Optimize traversal for in-place

Question

Given a binary tree, implement an in-place traversal algorithm that visits each node exactly once and returns the values in a specific order (e.g., in-order, pre-order, or post-order) without using any additional data structures. Your solution should operate with O(1) space complexity, modifying the tree structure only as necessary for traversal.

Codemia · Accepted Answer

To solve the problem of in-place traversal of a binary tree with O(1) space complexity, we can utilize the **Morris Traversal** technique. This algorithm is particularly suitable here because it allows us to visit each node without using a stack or recursion, effectively achieving the desired traversal order (in-order, pre-order, or post-order). The key idea is to temporarily modify the tree structure by creating links between nodes, enabling us to backtrack without additional space.

1. **Identify the traversal type**: For this example, we will implement an in-order traversal. 
2. **Initialization**: Start from the root of the tree. 
3. **Iterate through the tree**: While the current node is not null:  
   - If the current node has no left child, print the current node's value (or store it) and move to the right child.  
   - If it has a left child, find the rightmost node in the left subtree (the predecessor).  
   - Make the right child of the predecessor point to the current node (creating a link for backtracking).  
   - Move the current node to its left child.  
4. **Completion**: Repeat until all nodes have been visited.

**Example**: For a tree like this:
```
    1
   / \
  2   3
 / \
4   5
```
The in-order traversal output should be: 4, 2, 5, 1, 3.

Here's the Python implementation of the Morris In-Order Traversal:
```python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def morris_inorder_traversal(root):
    current = root
    result = []
    while current:
        if current.left is None:
            result.append(current.val)  # Visit the node
            current = current.right
        else:
            # Find the predecessor
            predecessor = current.left
            while predecessor.right and predecessor.right != current:
                predecessor = predecessor.right
            if predecessor.right is None:
                predecessor.right = current  # Create a link
                current = current.left
            else:
                predecessor.right = None  # Remove the link
                result.append(current.val)  # Visit the node
                current = current.right
    return result
```
This code performs an in-order traversal and returns the values in a list.

The time complexity of the Morris Traversal algorithm is O(n), where n is the number of nodes in the binary tree. This is because each node is visited exactly once. The space complexity is O(1) since we are not using any additional data structures for traversal. The only space used is for pointers, which does not grow with the input size.

1. **Empty Tree**: If the input tree is empty (i.e., root is None), the output should be an empty list. 
2. **Single Node**: If there is only one node, the output should simply be the value of that node. 
3. **Skewed Trees**: For highly unbalanced trees (either left-skewed or right-skewed), the algorithm should still work efficiently without additional space. 
4. **Tree with Duplicates**: The algorithm should correctly handle trees with duplicate values, visiting each node exactly once.

Optimize traversal for in-place

Slack

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

Slack 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