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?

Mishnah

Answer 1

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

Serene

Just realized that finding the predecessor for ALL the nodes in a binary tree will take time of o(n)... – Mishnah

Answer 2

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.

Tremendous

Why not 3 times? Isn't there also a 3rd/final time when it is visited, when the node it points to has its right-child [non-null] pointer reference (to what it is a predecessor of) re-set back to null (directly before printing current node)? I am referring to this line from the full algorithm: pre->right = NULL; – Aircraft

@Aircraft Your are right. There will be another visit to to a node when restoring the right child of the predecessor to null. I have updated my answer. – Tremendous

Thank you - your edits look good. I followed up and edited in a clarification that the black line is traveled twice (for both 2nd visit AND 3rd visit) - I'm not sure if you can see that edit yet, but let me know if you think I wrote something incorrectly. – Aircraft

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

Richardricharda

A node can be visited more than 3 times. E.g. in the tree [1, 2, 3, 4, 5, ..., 43] the node 5 will be visited 4 times. – Radiogram

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; 

Aircraft

FWIW: Wiki has a nice page on this algorithm too: Referred to there as "Threaded binary tree" – Aircraft

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.

Denture

Answer 6

The original text was written in Chinese：Morris-Traversal，You can navigate to that page and then translate it into English for a better reading experience.(The translation on the webpage is somewhat unreasonable; you can refer to this here for a better understanding.) For the Chinese text in the image, I have translated it below.

The main part of the time complexity originates from two core operations: traversing the nodes (via current) and finding the predecessor nodes for all nodes (pre).

1. Time complexity for operations on current:

   Each node is visited at most twice through current, once when moving down to the leftmost node, and another time when backtracking through the established temporary links. Therefore, the time complexity for operations on current is O(n).

   Nodes requiring backtracking are visited twice, while nodes not requiring backtracking are only visited once.

2. Finding the predecessor nodes for all nodes pre:

   The time complexity of finding the predecessor node for a single node is related to the height of the tree, which is O(log n). Therefore, intuitively, the overall time complexity of finding the predecessor nodes for all nodes in the entire algorithm process would be O(n * log n), but in reality, this process also has a time complexity of O(n).

   Take the following tree as an example: Example Tree

   In a binary tree, the predecessor node of any node can be found as follows: starting from the current node, move left once, then continuously move right until the end. The node reached in this way is its predecessor node.

   For example, with node 0, the search process is: first move left to node 1, then continue moving right, passing through nodes 4, 8, 12, 16, marking the path (marked as 0, indicating it is the path for finding the predecessor node of node 0). The same method is applied to other nodes, with corresponding edge markings.

   Every left link in the tree is traversed exactly once: for any left link connecting parent node a and child node b, it is only traversed when searching for the predecessor node of a.

   As for right links, they are traversed no more than once:

   Right links on the direct downward path from the root node along the right child nodes are not traversed, while the rest of the right links are exactly traversed once.

   Why right links are traversed no more than once

   The text in the top brown box: To find the predecessor of a node, one must first move one step to the left and then as far right as possible.

   The text in the left blue box: For the right links on this path, there is no node x that can reach by moving one step to the left and then traversing these right links.

   The text in the middle purple box: For the right links on the rest of the tree, there is a node x from which you can move one step to the left and then traverse these right links.

   The text in the right green box: Assuming a right link is traversed twice, such as the red link above, there must exist two nodes, x and y, that can first move one step to the left and then reach the same right link. This would mean the red node would have two parents, which contradicts the definition of a binary tree.

   Given that a binary tree with n nodes has n-1 edges, the time complexity of this process is O(n).

Therefore, the overall time complexity of the algorithm is O(n), where n is the total number of nodes in the tree.

Erythrocytometer