[ACCEPTED]-How is the time complexity of Morris Traversal o(n)?-binary-tree

The original paper for Morris traversal 25 is Traversing binary trees simply and cheaply. It claims that time complexity is O(n) in 24 Introduction section:

It is also efficient, taking 23 time proportional to the number of nodes 22 in the tree and requiring neither a run-time 21 stack nor 'flag' bits in the nodes.

The full 20 paper should have a analysis of time complexity. But 19 the full paper can't be accessed for free.

Morris Traversal方法遍历二叉树（非递归，不用栈，O(1)空间） does 18 some analysis. I have translated some relevant 17 part and made some corrections based on 16 my understanding. Here is my understanding:

A 15 n-node binary tree has n-1 edges. In a Morris 14 traversal, one edge is visited at most 3 13 times. 1st visit is for locating a node. 2nd 12 visit is for looking for the predecessor 11 of some node. And 3rd/final is for restoring 10 the right child of the predecessor to null. In 9 the following binary tree, red dashed line 8 is for locating a node (1st visit). Black 7 dashed line is for looking for predecessor 6 node (traveled two times: for both 2nd visit 5 AND 3rd visit). Node F will be visited when 4 being located. It will also be visited when 3 node H is looking for its predecessor. Finally, it 2 will be visited when restoring the right 1 child of node G (H's predecessor) to null.

it is not going to increase the complexity 6 as the algorithm just rebuilds the tree 5 in only one direction(rebuilding takes only 4 O(n) after which its only O(n) again to 3 print them... but they have merged both 2 the functionality into a same function and 1 gave a special name for the algo thats it...

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

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

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

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

Now to answer your 8 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 7 though it may have sounded like I was implying 6 above that the entire algorithm runtime is 2n, it is not - it 5 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 4 line (from the full algorithm) to remove 3 the old predecessor "thread" reference is 2 strictly necessary (although it doesn't 1 hurt, and can be considered nice tidying-up):

pre->right = NULL; 

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

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

1. the current visits the node.

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

2. build a loop and destroy the 8 loop.

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

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

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