binary-tree

How is the time complexity of Morris Traversal o(n)?

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?

Solution

  • 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...