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 … Read more