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

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

Another way of looking at it is to find out how many times a tree node will be traversed. As it is constant(3 times for a binary tree). We are looking at O(n).

Answer 4

First, I have a correction to make to a claim that you made:

In the traversal, whenever the node has a left child a copy of it is made to the right child of its predecessor

A copy of the [current] node is not made to the right child of its [current node's] predecessor - the right child of current node's predecessor is pointed to current node - a pointer does not make any copy; instead it just points to the current node that already exists.

Now to answer your question about your code snippet:

while(pre->right != NULL && pre->right != current)
        pre = pre->right;

• That loop does add time to the running of the algorithm [compared to if that loop were not in the code]
• But in a worst case, the time it adds is exactly n (taking the run time from n to 2n). This worst case happens when every single node must be visited an extra time, in order to find all predecessors; by the way, each such extra visit of a given node is the only extra time it is visited when finding predecessors (that's because finding any other predecessor will never travel over the same nodes that were traveled through to find any other predecessor) - that explains why the extra time contributes going from n -> 2n [linear] but not n -> n^2 [quadratic]
• Even though 2n > n, when [Big-O] complexity is considered, O(2n) = O(n)
• In other words, taking longer time of 2n compared to n is not actual extra complexity: n & 2n runtimes both have complexities of identical O(n) [they are both "linear"]

Now even though it may have sounded like I was implying above that the entire algorithm runtime is 2n, it is not - it is actually 3n.

• The loop that is in just the code snippet itself contributes n time
• But the algorithm as a whole runs in 3n because each node is visited at most 3 times {once/first to "thread" it back to the node that it is a predecessor of (the ultimate goal that the code snippet helps achieve); a 2nd time when it is arrived at in otherwise normal traversal [as opposed to anything to do with predecessor threading]; and then a 3rd/final time when it is found as predecessor [that itself for the 2nd/final time] again and its right-child pointer/thread is removed from pointing to right-child of current node [directly before printing current node]}
• And again [just as complexity O(2n) = O(n)], complexity O(3n) = O(n)
• So to summarize: Yes, your code snippet loop does contribute time, but NOT extra time complexity

By the way, I don't think this line (from the full algorithm) to remove the old predecessor "thread" reference is strictly necessary (although it doesn't hurt, and can be considered nice tidying-up):

pre->right = NULL; 

Answer 5

I discuss Morris inorder traversal here, because one node can be visited at most 4 times, so the time complexity is O(n).

Let's divide the types that one node is visited into two types:

1. the current visits the node.

   If one node has left child, current visits twice, otherwise visits once.

2. build a loop and destroy the loop.

   If one node is in a loop, it is visited twice, otherwise zero.

I draw the figure below and use A + B to represent the times, A is current, B is loop.

For the node D, current moves from B to Dand from E to D. D is also in the loop A B D F G, D is visited when current move from A to B(build the loop) and from A to H(destroy the loop). Therefore, node D is visited 2 + 2 = 4 times.