Java 5 ms Morris Traversal Solution: average O(1) time & O(1) space


  • 0
    Z

    The Morris Traversal time complexity for traversing all n nodes is O(n), and the averaged time complexity for getting each node is O(1); the space complexity is O(1) for storing only the current node. Using the Morris Traversal method to perform an inorder traversal on BST will generate the sorted array.
    In this case, next() function requires the next smallest element to be returned, so we break the traversing loop every time a node is traversed.

    public class BSTIterator {
        
        private TreeNode root,cur;
        public BSTIterator(TreeNode root) {
            root = root;
            cur = root;
        }
    
        /** @return whether we have a next smallest number */
        public boolean hasNext() {
            return cur != null;
        }
    
        /** @return the next smallest number */
        public int next() {
            int r = 0;
            while(cur!=null){
                if(cur.left==null){
                    r = cur.val;
                    cur = cur.right;
                    // Got the node, break loop
                    break;
                }else{
                    TreeNode node = cur.left;
                    while(node.right!=null&&node.right!=cur){
                        node  = node.right;
                    }
                    if(node.right==null){
                        node.right = cur;
                        cur = cur.left;
                    }else{
                        node.right = null;
                        r = cur.val;
                        cur = cur.right;
                        // Got the node, break loop
                        break;
                    }
                }
            }
            return r;
        }
    }
    

Log in to reply
 

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