Morris Traversal: An Ingenious Space-Efficient Tree Traversal Algorithm

By Anudeep Balla

Tree traversal is a fundamental operation in computer science, frequently employed to explore the nodes of tree data structures. Among the various traversal methods, Morris Traversal stands out as a space-efficient algorithm designed by J. H. Morris in 1979. We’ll delve into the Morris Traversal algorithm, understand its principles, and explore a couple of problems, complete with problem statements and Java solutions.

Understanding Morris Traversal:

Morris Traversal is an in-order tree traversal algorithm that doesn’t rely on recursion or additional data structures like stacks. The ingenious idea behind Morris Traversal is to modify the tree structure during traversal, effectively eliminating the need for extra space. This results in a constant space complexity algorithm, making it an efficient choice for in-order traversals.

Algorithm

• Initialize the root as the current node curr.
• While curr is not NULL, check if curr has a left child.
• If curr does not have a left child, print curr and update it to point to the node on the right of curr.
• Else, make curr the right child of the rightmost node in curr's left subtree.
• Update curr to this left node.

Example: