Morris Traversal-Time O(n), Space O(1), inorder, preorder, postorder


  • 0
    H

    Morris Traversal is a way of traversing BST with O(1) space and O(n) time. It's a little hard to understand but the basic idea is to link predecessor back to current node so that we can trace back to top of BST. It's also a little tricky to see how it is O(n) since finding predecessor is often O(logn). The answer is , we don't have to find predecessor for every node, only the nodes with valid left child. It will be obvious if you draw a tree to see that every edge is only visited constant time.

    Inorder

        def inorderTraversal(self, root):
            result=[]
            node=root
            while node!=None:
                if node.left==None:
                    result.append(node.val)
                    node=node.right
                else:
                    pre=node.left
                    while pre.right!=None and pre.right!=node:
                        pre=pre.right
                    if pre.right==None:
                        pre.right=node
                        node=node.left
                    else:
                        pre.right=None
                        result.append(node.val)
                        node=node.right
            return result
    

    Preorder, basically the same, just one line of change

        def preorderTraversal(self, root):
            result=[]
            node=root
            while node!=None:
                #print(node.val)
                if node.left==None:
                    result.append(node.val)
                    node=node.right
                else:
                    pre=node.left
                    while pre.right!=node and pre.right!=None:
                        pre=pre.right
                    if pre.right==None:
                        result.append(node.val)
                        pre.right=node
                        node=node.left
                    else:
                        pre.right=None
                        node=node.right
            return result
    

    Postorder, this is a little tricky, you have to output path along predecessor in reverse order.

        def postorderTraversal(self, root):
            result=[]
            def reverseOrder(left,right):
                while left<right:
                    result[left],result[right]=result[right],result[left]
                    left+=1
                    right-=1
            dummynode= TreeNode(None) #dummy node
            node=dummynode
            node.left=root
            while node!=None:
                print(node.val)
                if node.left==None:
                    node=node.right
                else:
                    pre=node.left
                    while pre.right!=None and pre.right!=node:
                        pre=pre.right
                    if pre.right==None:
                        pre.right=node
                        node=node.left
                    else:
                        pre=node.left
                        count=1
                        while pre.right!=None and pre.right!=node:
                            result.append(pre.val)
                            pre=pre.right
                            count+=1
                        result.append(pre.val)
                        pre.right=None
                        reverseOrder(len(result)-count,len(result)-1)
                        node=node.right
                        
            return result
    

Log in to reply
 

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