Why BST and not Binary Tree?


  • 0
    A

    I solved this problem by using a stack (other users have already posted similar solutions).

    /**
     * Definition for binary tree
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    
    public class BSTIterator {
        
        
        Deque<TreeNode> stack = new ArrayDeque<>();
    
        public BSTIterator(TreeNode root) {
            while (root != null) {
                stack.addFirst(root);
                root = root.left;
            }
        }
    
        /** @return whether we have a next smallest number */
        public boolean hasNext() {
            return !stack.isEmpty();
        }
    
        /** @return the next smallest number */
        public int next() {
            TreeNode node = stack.pop();
            int result = node.val;
            if (node.right != null) {
                node = node.right;
                while (node != null) {
                    stack.push(node);
                    node = node.left;
                }
            }
            return result;
        }
    }
    
    /**
     * Your BSTIterator will be called like this:
     * BSTIterator i = new BSTIterator(root);
     * while (i.hasNext()) v[f()] = i.next();
     */
    

    However, in this solution, I don't take into account that I am traversing a binary search tree; the solution should work with any binary tree.

    Therefore, given that the problem statement mentions BST, I am wondering whether there is any way to take advantage of the BST properties and come up with a more efficient solution.


  • 0
    W

    The next() function is supposed to return the next smallest number. A BST makes that very easy to do since an in order traversal of the tree works. It won't be so easy with just a binary tree since there's no ordering or structure to the tree.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.