Topic describes

Binary search tree iterator

Implement a binary search tree iterator class BSTIterator, representing an iterator that traverses the binary search tree (BST) in middle order, including hasNext() method (returns the value of the next node), hasNext() method (returns whether the whole tree has been traversed).

The sample

Using the binary search tree iterator for this tree should return:

BSTIterator bSTIterator = new BSTIterator([7.3.15.null.null.9.20]);
bSTIterator.next();    / / return 3
bSTIterator.next();    / / return 7
bSTIterator.hasNext(); / / return True
bSTIterator.next();    / / return
bSTIterator.hasNext(); / / return True
bSTIterator.next();    / / return to 15
bSTIterator.hasNext(); / / return True
bSTIterator.next();    / / return 20
bSTIterator.hasNext(); / / returns False
Copy the code

Advanced requirements: The amortized time of next() and hasNext() operations is O(1), and O(h) memory is used. Where h is the height of the tree.

answer

Since it is a binary search tree, it is inevitable to leave the middle order traversal. There are generally recursive and non-recursive implementation methods, among which the recursive implementation of the middle order traversal is relatively simple:

function inorderTraversal(root){
    if(root.left) inorderTraversal(root.left)
    console.log(root.val) // Operate the node here
    if(root.right) inorderTraversal(root.right)
}
Copy the code

The next() method returns a node in a queue and returns its val value. The hasNext() method simply returns whether the queue is empty.

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */
/ * * *@param {TreeNode} root* /
const BSTIterator = function(root) {
    this.queue = []
    const inorderTraversal = (root) = > {
        if(root.left) inorderTraversal(root.left)
        this.queue.push(root)
        if(root.right) inorderTraversal(root.right)
    }
    inorderTraversal(root)
};

/ * * *@return {number}* /
BSTIterator.prototype.next = function() {
    return this.queue.shift().val
};

/ * * *@return {boolean}* /
BSTIterator.prototype.hasNext = function() {
    return!!!!!this.queue.length
};

/** * Your BSTIterator object will be instantiated and called as such: * var obj = new BSTIterator(root) * var param_1 = obj.next() * var param_2 = obj.hasNext() */
Copy the code

Complexity analysis: This solution stores all nodes in a queue, so the spatial complexity is O(n), and the time complexity of both the next() and hasNext() methods is O(1).

If the tree is traversed nonrecursively, there is no need to traverse the entire tree in the constructor. The non-recursive implementation is as follows:

function inorderTraversal(root){
    const stack = [];
    let cur = root
    while(cur){
        stack.push(cur)
        cur = cur.left
    }
    while(stack.length){
        const node = stack.pop()
        console.log(node.val) // Operate the node here
        cur = node.right
        while(cur){
            stack.push(cur)
            cur = cur.left
        }
    }
}
Copy the code

In this case, to traverse non-recursively, just use a stack to hold a small number of nodes:

var BSTIterator = function(root) {
    this.stack = []
    var cur = root
    while(cur){
        this.stack.push(cur)
        cur = cur.left
    }
};
BSTIterator.prototype.next = function() {
    var node = this.stack.pop()
    if(node.right){
        var cur = node.right
         while(cur){
            this.stack.push(cur)
            cur = cur.left
        }
    }
    return node.val
};
BSTIterator.prototype.hasNext = function() {
    return!!!!!this.stack.length
};
Copy the code

Complexity analysis: Only one stack is used to store the nodes with the maximum number of tree height, so the space complexity is O(h), and the time complexity of the next() and hasNext() methods is O(1).