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

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.

enter image description here


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


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

Tags:

Binary Tree