Morris Traversal: Space Efficient Way to Traverse Binary Trees | Threaded BT

Agenda:

1. Quick Intro
2. Why?
3. Understanding Morris Traversal: The Threaded Binary Tree
4. Advantages
5. Drawbacks
6. Implementation in Python
7. Time & Space Complexity
8. Conclusion

Quick Intro

• Morris Traversal is a clever tree traversal algorithm that allows us to traverse a binary tree in CONSTANT SPACE. (i.e. without recursion or an explicit stack).

Why?

• When dealing with binary trees, traditional traversal methods like In-order, Pre-order, and post-order often require additional space proportional to the height of the tree, primarily for the recursion stack.
• This space complexity can be a limitation in memory-constrained environments.

Understanding Morris Traversal: The Threaded Binary Tree

• Named after its inventor, Joseph M. Morris, this traversal technique leverages the concept of threading the binary tree.
• Threading the binary tree means it uses threads or links pointing to ancestor nodes. These threads allow us to move back to the parent of a subtree without extra space.
• Here's a closer look at how it works:

1. In-order Morris Traversal Algo:
   • Start at the root node.
   • For each node, check if it has a left child:
     • If not, visit the node and move to the right child.
     • If it has a left child, find the rightmost node in the left subtree (inorder predecessor).
       • If the rightmost node’s right pointer is None, set it to point to the current node and move to the left child.
       • If the rightmost node’s right pointer is already set to the current node, reset it to None, visit the current node, and move to the right child.
2. Pre-order Morris Traversal Algo:
   • Start at the root node.
   • For each node, check if it has a left child:
     • If not, visit the node and move to the right child.
     • If it has a left child, find the rightmost node in the left subtree (in-order predecessor).
       • If the rightmost node’s right pointer is None, set it to point to the current node, visit the current node, and move to the left child.
       • If the rightmost node’s right pointer is already set to the current node, reset it to None and move to the right child.

The key to both these traversals is the temporary modification of the tree structure to include threads that allow revisiting nodes without using extra space.

Advantages of Morris Traversal

• Space Efficiency: The most significant advantage is its O(1) space complexity, which is achieved by modifying the tree itself rather than using additional data structures.
• In-place Operation: Since the tree is modified temporarily, there is no need for extra space allocation, making it ideal for environments with strict memory constraints.

Drawbacks of Morris Traversal

• Tree Modification: The primary drawback is the modification of the tree structure during traversal, which can be problematic in situations where the tree must remain unaltered. This requires careful handling to ensure the tree is restored to its original state after traversal.
• Complexity: The logic behind threading and unthreading the tree can be more complex compared to traditional methods, making it slightly harder to implement and debug.

Implementation in Python

Here’s how you can implement both In-order and Preorder Morris Traversal in Python:

In-order Morris Traversal:

class TreeNode:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

def morris_inorder_traversal(root):
    current = root
    while current:
        if not current.left:
            print(current.val, end=" ")
            current = current.right
        else:
            predecessor = current.left
            while predecessor.right and predecessor.right is not current:
                predecessor = predecessor.right

            if not predecessor.right:
                predecessor.right = current
                current = current.left
            else:
                predecessor.right = None
                print(current.val, end=" ")
                current = current.right

# Example usage
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.right = TreeNode(6)

morris_inorder_traversal(root)

Pre-order Morris Traversal:

def morris_preorder_traversal(root):
    current = root
    while current:
        if not current.left:
            print(current.val, end=" ")
            current = current.right
        else:
            predecessor = current.left
            while predecessor.right and predecessor.right is not current:
                predecessor = predecessor.right

            if not predecessor.right:
                print(current.val, end=" ")
                predecessor.right = current
                current = current.left
            else:
                predecessor.right = None
                current = current.right

# Example usage
morris_preorder_traversal(root)

Complexity

• Time: O(N) -- Linear
• Space: O(1) -- Constant

Conclusion

• Morris Traversal stands out in scenarios where space efficiency is paramount.
• While it introduces some complexity due to tree modifications, its ability to achieve traversal with O(1) space complexity makes it a valuable.