CODEWITHSUNDEEP
algorithmbinary-tree
Leo Ming Zhong
Leo Ming Zhong

Reputation: 21

Runtime of Morris inorder tree traversal algorithm

I just learned about the Morris inorder tree traversal algorithm. But I haven't found any analysis of the running time of this algorithm. Can someone give a runtime analysis of this algorithm? This link explains how Morris algorithm work. Thanks~~ Explain Morris inorder tree traversal without using stacks or recursion

Upvotes: 1

Views: 799

Answers (1)

Gene
Gene

Reputation: 46960

That's probably because it's so simple to deduce. There is a constant amount of work at every visit. No node is visited more than three times (for a binary tree), so it's trivially O(n) where n is the number of nodes.

Upvotes: 4

Related Questions