Binary Search Tree Iterator

Design an iterator over a binary search tree with the following rules:

  • Elements are visited in ascending order (i.e. an in-order traversal)
  • next() and hasNext() queries run in O(1) time in average.

Example

For the following binary search tree, in-order traversal by using iterator is [1, 6, 10, 11, 12]

   10
 /    \
1      11
 \       \
  6       12

Challenge

Extra memory usage O(h), h is the height of the tree.

Super Star: Extra memory usage O(1)

1. Inorder Traverse the BST into an arrayList – O(n) space and O(n) time

public class Solution {
    //@param root: The root of binary tree.
    ArrayList<TreeNode> nodes;
    int index;
    public Solution(TreeNode root) {
        //flattern the tree using in-order traversal
        nodes = new ArrayList<>();
        inOrderTraversal(root, nodes);
        index = 0;
    }

    public void inOrderTraversal(TreeNode root, ArrayList<TreeNode> result) {
        if (root == null) {
            return;
        }
        inOrderTraversal(root.left, result);
        result.add(root);
        inOrderTraversal(root.right, result);
    }

    //@return: True if there has next node, or false
    public boolean hasNext() {
        return index < nodes.size();
    }

    //@return: return next node
    public TreeNode next() {
        if (index < nodes.size()) {
            return nodes.get(index++);
        }
        return null;
    }
}

2. O(h) space – h is the height of the tree
Have a stack which only contains the left-most nodes and its ancestors, so that it takes O(h) space. And for each node, the average time complexity for next() is O(1).(Since the total time complexity is O(n))

public class Solution {
    //@param root: The root of binary tree.
    Stack<TreeNode> nodes;
    public Solution(TreeNode root) {
        nodes = new Stack<>();
        TreeNode runner = root;
        while (runner != null) {
            nodes.push(runner);
            runner = runner.left;
        }
    }

    //@return: True if there has next node, or false
    public boolean hasNext() {
        return !nodes.empty();
    }

    //@return: return next node
    public TreeNode next() {
        if (!nodes.empty()) {
            TreeNode curr = nodes.pop();
            if (curr.right != null) {
                TreeNode runner = curr.right;
                while (runner != null) {
                    nodes.push(runner);
                    runner = runner.left;
                }
            }
            return curr;
        }
        return null;
    }
}

3. O(1) space

FacebookTwitterGoogle+Share

Leave a Reply

Your email address will not be published. Required fields are marked *