Java Solution using Morris in-order traversal method: O(1) for space and O(1) for hasNext and amortized O(1) for next()


  • 0
    F

    I noticed that no one mentioned the Morris in-order traversal method so I posted it here. The memory space can be reduced to O(1). Also it's easy to get O(1) for hasNext() but not so obvious for next(). I didn't do a careful calculation of the time-complexity for next() method. But I believe it should be O(1) on average.

    Here is the code:

    public class BSTIterator {	
         TreeNode currNode;   // refer to the node currently having the smallest value
         TreeNode preNode;    // auxiliary TreeNode variable
    
         public BSTIterator(TreeNode root) {
             preNode = root;
             currNode = root;
            
             // initialize the currNode to the node with the smallest value (basically the "leftmost" node)
        	 if (currNode != null) {   		
        	     while (currNode.left != null) {
        		 preNode = currNode.left;   // go to the left subtree
    
        		 while (preNode.right != null) {
        		     preNode = preNode.right;    // find the "rightmost" node
        		 }
    
                     preNode.right = currNode;   // modify the BST structure 
        		 currNode = currNode.left;   // and continue with the left subtree
        	     }   		
             }		
         }
    
         public boolean hasNext() {	
        	 return currNode != null;    // if currNode is null, we reach the end of the BST
         }
    
         public int next() { 
        	 int currVal = currNode.val; // store the current smallest value to return later
        	
        	// move currNode to refer to the next smallest value   	
        	 currNode = currNode.right;  // start from the right child node of current node
    
        	 while (currNode != null) {  
        	     if (currNode.left == null) {  // if the left child node is null, then we're done
        		 break;
        	     }
    
        	     preNode = currNode.left;      // else we need to find the "rightmost" node of the left subtree
    
        	     while (preNode.right != null && preNode.right != currNode) {
        		 preNode = preNode.right;
        	     }
    
        	     if (preNode.right == null) {  
        		 preNode.right = currNode;  // we found the "rightmost" node, modify the BST structure
        		 currNode = currNode.left;   // and continue with the left subtree
    
        	     } else {                     
        		 preNode.right = null;  // we are done with the left subtree, so restore the BST structure
        		 break;
        	     }
        	 }  	
           	
             return currVal;    // return the smallest value saved earlier
         }   
    }
    

  • 0
    S
    This post is deleted!

Log in to reply
 

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