My Java Solution with O(1) space and O(1) amortized time, using Morris Tree Traversal


  • 7
    O

    First of all, even with most optimized space and time complexity, I have to say this may be not the best solution, since it changes the tree structure a little bit during constructor period.

    #Construct Period
    The idea is use in-order Morris Tree Traversal (check out [1][2] if you are not familiar with it, otherwise the bellow explanation to you is nonsense) to construct a threaded binary tree in construct function. (This is O(n) time, but we don't care much about it.) Then set a pointer (we call it "curr") to the smallest TreeNode, which is easy to do, just find the left-most child from root.

    #hasNext()
    For hasNext() function, simple return "curr != null", which is by definition of threaded binary tree.

    #next()
    For next() function, it is a little bit tricky. We call the right child of "curr" as "next". If "next" is not a normal right child of "curr", which means the right child relationship is constructed during the threaded binary tree construction period, then the next TreeNode we should iterate is indeed "next". However, if "next" is a normal right child of "curr", then the next TreeNode we should iterate is actually the left-most child of "next".

    So the problem reduces to how to make clear the situation. Well, it is no hard. If "next" is null, then we've done, simply set "curr" to null. If "next" has no left child, or "next"'s left child is strictly larger than "curr", that means it is a normal right child of "curr", so we should set "curr" to left-most child of "next". Otherwise, we set "curr" to "next", and break the right child relationship between "curr" and "next", to recover the original tree structure.

    #Complexity analysis
    The space complexity is straightforwardly O(1). The time complexity needs some more explanation. Since the only part that is not O(1) is when we search the left-most child of "next". However, for all the children along this left path (say, there are N children), we do once search left-most and (N-1) times simply go to right child. So the amortized time complexity is still O(1).

    #Code:

    public class BSTIterator {
    
    	private TreeNode curr;
        public BSTIterator(TreeNode root) {
    		TreeNode prev;
    		//Do a morris in-order traversal, to construct a threaded binary tree
    		curr = root;
    		while(curr != null){
    			if(curr.left == null){
    				curr = curr.right;
    			}
    			else{
    				prev = curr.left;
    				while(prev.right != null && prev.right != curr)
    					prev = prev.right;
    
    				if(prev.right == null){
    					prev.right = curr;
    					curr = curr.left;
    				}
    				else{
    					curr = curr.right;
    				}
    			}
    		}
    
    		//get the left-most child of root, i.e. the smallest TreeNode
    		curr = root;
    		while(curr != null && curr.left != null)
    			curr = curr.left;
        }
    
        /** @return whether we have a next smallest number */
        public boolean hasNext() {
    		return curr != null;
        }
    
        /** @return the next smallest number */
        public int next() {
    
    		//copy the value we need to return
    		int result = curr.val;
    
    		TreeNode next = curr.right;
    		if(next == null)
    			curr = next;
    		//the right child relationship is a normal one, find left-most
    		//child of "next"
    		else if(next.left == null || next.left.val > curr.val){
    			curr = next;
    			while(curr.left != null)
    				curr = curr.left;
    		}
    		//the right child relationship is made when we
    		//construct the threaded binary tree
    		else{
    			curr.right = null;//we recover the original tree structure
    			curr = next;
    		}
    
    		return result;
        }
    }
    

    #Reference

    For those who are not familiar with Morris Tree Traversal, these two paragraphs are good references.

    [1]https://en.wikipedia.org/wiki/Threaded_binary_tree

    [2]http://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion-and-without-stack/


  • 0
    M

    For the constructor, I don't see how you constructed threaded binary tree. Instead, "prev.right = null;" already recovers the tree after Morris Traversal. Can you illustrate what's the point of doing a complete traversal in the constructor while the tree is recovered afterwards? Thanks.


  • 0
    O

    Hi, I just fixed that problem, thanks for mention that. Now the code is totally fine.


  • 0
    M

    Hey, just saw your post. I got similar idea but slightly improved the time cost from O(1) amortized time to O(1) in worst case.

    Check it here.
    https://leetcode.com/discuss/63980/o-1-time-o-1-space-in-worst-case-challenge-me-please


  • 0
    O

    Hey mhhh:
    This is great! Thanks I learnt a lot from your code.


Log in to reply
 

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