Simple Java solution using a Stack O(h) space.


  • 0
    M

    The left most node in a BST has the smallest value. So we store all the nodes that lead to the left most node in a stack. This gives us a O(h) space. Then when we take an element from the stack we traverse through the right node of that element and go left all the way and store the values in a stack, if a right node exist else we don't do anything to the stack.

    /**
     * Definition for binary tree
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    
    public class BSTIterator {
        Stack<TreeNode> s = new Stack<TreeNode>();
    
        public BSTIterator(TreeNode root) {
            if(root!=null){
                traverseLeft(root);
            }
            
            
        }
        //Traverse to the left most node and store all the nodes on the stack as you go.
        public void traverseLeft(TreeNode root){
            s.push(root);
            while(root.left!=null){
                s.push(root.left);
                root=root.left;
            }
        }
    
        /** @return whether we have a next smallest number */
    //If the stack is empty it means that we still have elements to traverse.     
    public boolean hasNext() {
            return !s.isEmpty();
        }
    
        /** @return the next smallest number */
    //Take the top most element from the stack. This is the element that must be returned. Before you return store the right node(if it exist) in the stack and traverse through all of the left nodes in the right node and store them in the stack. 
        public int next() {
            TreeNode popedOut=s.pop();
            if(popedOut.right!=null){
                traverseLeft(popedOut.right);
            }
            
            return(popedOut.val);
            
        }
    }
    
    

Log in to reply
 

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