Optimize traversal for O(1) space

Question

Given a binary tree, implement an algorithm to traverse the tree in-order while using O(1) space. Your solution should not utilize recursion or any additional data structures, and it should return the values of the nodes in the order they are visited.

Codemia · Accepted Answer

To traverse a binary tree in-order (left, root, right) while using O(1) space, we can utilize the Morris Traversal algorithm. This approach leverages the tree's structure by modifying the tree temporarily to create a threaded binary tree. This allows us to traverse the tree without recursion or additional data structures. The Morris Traversal works by utilizing the right pointers of the tree nodes to create temporary links to the in-order predecessor, enabling us to traverse back to the parent node without using the call stack or extra space.

1. Start with the current node set to the root of the binary tree.
2. If the current node has no left child, print the current node's value and move to its right child.
3. If the current node has a left child, find the in-order predecessor of the current node. The in-order predecessor is the rightmost node in the left subtree.
4. If the right child of the predecessor is null, set it to point to the current node (creating a temporary link), print the current node's value, and move to the left child.
5. If the right child of the predecessor is already pointing to the current node, it means we have completed the left subtree, so we set it back to null and move to the right child.
6. Repeat the process until all nodes have been visited.

**Example:** Given the binary tree:
```
    1
   / \
  2   3
 / \
4   5
```
The traversal sequence would be: 4, 2, 5, 1, 3.

```python
def morris_inorder_traversal(root):
    current = root
    result = []
    while current:
        if current.left is None:
            result.append(current.val)
            current = current.right
        else:
            # Find the in-order predecessor
            predecessor = current.left
            while predecessor.right and predecessor.right != current:
                predecessor = predecessor.right
            # Make current as the right child of its predecessor
            if predecessor.right is None:
                predecessor.right = current
                current = current.left
            else:
                # Revert the changes made to restore the original tree
                predecessor.right = None
                result.append(current.val)
                current = current.right
    return result
```

The time complexity of the Morris Traversal is O(n), where n is the number of nodes in the binary tree, as each node is visited at most twice. The space complexity is O(1) because we do not use any additional data structures or recursion stack. This is optimal for the problem constraints, as we are required to use constant space.

1. **Empty Tree:** If the root is None, the function should return an empty list. This is a straightforward case that should be handled at the beginning of the traversal function.
2. **Single Node Tree:** If the tree consists of only one node, the function should return a list containing that single node's value.
3. **Skewed Trees:** For trees that are skewed (all nodes on one side), the algorithm should still work, returning the nodes in the correct in-order sequence without additional space.

Optimize traversal for O(1) space

Palantir

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Palantir Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string