Menu
http://geeksforgeeks.org/?p=6358 Can anyone please explain how Morris Traversal has a time complexity of o(n)? In the traversal, whenever the node has a left child a copy of it is made to the right child of its predecessor. So worst case is that predecessor has to be found for each node
while(pre->right != NULL && pre->right != current) pre = pre->right; Which is going to increase the time complexity? Am I missing anything here?
794
Using Morris Traversal, we can traverse the tree without using stack and recursion. The idea of Morris Traversal is based on Threaded Binary Tree. In this traversal, we first create links to Inorder successor and print the data using these links, and finally revert the changes to restore original tree.
In general, time complexity is O(h) where h is height of BST. Insertion: For inserting element 0, it must be inserted as left child of 1. Therefore, we need to traverse all elements (in order 3, 2, 1) to insert 0 which has worst case complexity of O(n). In general, time complexity is O(h).
In-order, Pre-order, and Post-order traversals are Depth-First traversals. For a Graph, the complexity of a Depth First Traversal is O(n + m), where n is the number of nodes, and m is the number of edges. Since a Binary Tree is also a Graph, the same applies here.
But if we are talking about job interviews, then yes. The Morris algorithm for inorder traversal allows you to traverse a tree with O(n) time and O(1) space complexity.
The original paper for Morris traversal is Traversing binary trees simply and cheaply. It claims that time complexity is O(n) in Introduction section:
It is also efficient, taking time proportional to the number of nodes in the tree and requiring neither a run-time stack nor 'flag' bits in the nodes.
The full paper should have a analysis of time complexity. But the full paper can't be accessed for free.
Morris Traversal方法遍历二叉树（非递归，不用栈，O(1)空间） does some analysis. I have translated some relevant part and made some corrections based on my understanding. Here is my understanding:
A n-node binary tree has n-1 edges. In a Morris traversal, one edge is visited at most 3 times. 1st visit is for locating a node. 2nd visit is for looking for the predecessor of some node. And 3rd/final is for restoring the right child of the predecessor to null. In the following binary tree, red dashed line is for locating a node (1st visit). Black dashed line is for looking for predecessor node (traveled two times: for both 2nd visit AND 3rd visit). Node F will be visited when being located. It will also be visited when node H is looking for its predecessor. Finally, it will be visited when restoring the right child of node G (H's predecessor) to null.
147
it is not going to increase the complexity as the algorithm just rebuilds the tree in only one direction(rebuilding takes only O(n) after which its only O(n) again to print them... but they have merged both the functionality into a same function and gave a special name for the algo thats it...
21
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
