O(1) space Java solution using Morris Traverse


  • 0

    Re: Morris traverse solution

    As a follow-up in Lintcode, extra space usage O(1) is required which reminds me of Morris Traverse. For anyone who doesn't know Morris traverse, I really recommend you this magic traversal approach. And also you can try to get to know it by the code and comments in the following.

        private TreeNode cur;
        
        public BSTIterator(TreeNode root) {
            this.cur = root;
        }
    
        public boolean hasNext() {
            return cur != null;
        }
        
        public int next() {
            TreeNode node = null;
            while (cur != null && node == null) {
                if (cur.left == null) {         // no left child, then go right (right child or back to root)
                    node = cur;
                    cur = cur.right;
                } else {
                    TreeNode rmost = cur.left;
                    while (rmost.right != null && rmost.right != cur) rmost = rmost.right;
                    
                    if (rmost.right == null) {  // 1.link rmost to root (cur) as footprint before go left
                        rmost.right = cur;
                        cur = cur.left;
                    } else {                    // 2.We already get back to root by footprint, so restore then go right
                        node = cur;
                        rmost.right = null;
                        cur = cur.right;
                    }
                }
            }
            return node.val;
        }
    

    Note that the key of the algorithm is: link right pointer of rightmost child of left subtree before go left, so that when we complete left subtree we can follow the footprint back to root. Then restore rightmost's right pointer and then go for right subtree.

    Therefore, as the solution using Stack, the time complexity is O(1) amortized, but we only maintain current node rather than an entire stack.


Log in to reply
 

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