O(1) space with same time complex of Stack solution - Morris Traversal of Tree


  • 2
    J

    The Stack solution seems use O(h) space well the time complex of next() function is more than O(1).
    I try to use Morris Tree Traversal to solve this issue which saves space. However the time complex of construction of the class BSTIterator is O(n) (instead of O(h) to building the Stack). Time complex of next() function keep the same, between O(1) and O(h), since we are always have to find the right child node's most left child.

    /**
     * Definition for binary tree
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    
    public class BSTIterator {
        private TreeNode head = null;
        
        public BSTIterator(TreeNode root) {
            TreeNode pre = null;
            TreeNode cur = root;
            while (cur != null) {
                if (cur.left != null) {
                    pre = cur.left;
                    while (pre.right != null && pre.right != cur) {
                        pre = pre.right;
                    }
                    if (pre.right == null) {
                        pre.right = cur;
                        cur = cur.left;
                    } else {
                        cur = cur.right;
                    }
                } else {
                    if (head == null) head = cur;
                    cur = cur.right;
                }
            }
        }
    
        /** @return whether we have a next smallest number */
        public boolean hasNext() {
            return head != null;
        }
    
        /** @return the next smallest number */
        public int next() {
            int ret = head.val;
            TreeNode nextNode = head.right;
            if (nextNode != null) {
                while (nextNode.left != null && nextNode.left.val > head.val) {
                    nextNode = nextNode.left;
                }
            } 
            head = nextNode;
            
            return ret;
        }
    }
    
    /**
     * Your BSTIterator will be called like this:
     * BSTIterator i = new BSTIterator(root);
     * while (i.hasNext()) v[f()] = i.next();
     */
    

Log in to reply
 

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