Optimize traversal for in-place

Question

Given a binary tree, optimize the traversal to perform in-place modifications on the tree nodes without using additional space. Your task is to traverse the tree in a specified order (pre-order, in-order, or post-order) and update each node's value based on a defined rule, while ensuring that the traversal maintains O(n) time complexity. Return the modified tree structure after the traversal is complete.

Codemia · Accepted Answer

The problem requires us to traverse a binary tree and perform in-place modifications on the nodes while maintaining a specific order (pre-order, in-order, or post-order). Given the constraint of not using additional space, we can utilize the Morris Traversal technique, which is a tree traversal method that allows us to achieve O(n) time complexity with O(1) space. This technique is particularly useful for in-order and pre-order traversals. In this problem, we will choose pre-order traversal for its simplicity in modifying the node values as we visit them.

1. **Define the Rule**: Let's say we want to update each node's value to double its original value.  
2. **Use Morris Traversal**: Start from the root node. For each node, check if it has a left child. If it does, find the rightmost node in the left subtree to link back to the current node.  
3. **Modify and Traverse**: When visiting a node, modify its value (double it in our case). If the left child exists, link it to the current node to create a temporary connection.  
4. **Continue Traversal**: If no left child exists, move to the right child directly.  
5. **Revert Changes**: Make sure to restore the original tree structure after modifications are done.  
**Example**: For a tree with root value 1, left child 2, and right child 3, after traversal, the values would be updated to 2, 4, and 6 respectively.

```python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def modify_tree(root):
    current = root
    while current:
        if current.left is None:
            current.val *= 2  # Modify the current node's value
            current = current.right  # Move to right child
        else:
            # Find the inorder predecessor (rightmost node in left subtree)
            predecessor = current.left
            while predecessor.right and predecessor.right != current:
                predecessor = predecessor.right
            # Create a temporary link to the current node
            if predecessor.right is None:
                predecessor.right = current
                current.val *= 2  # Modify the current node's value
                current = current.left  # Move to left child
            else:
                predecessor.right = None  # Restore the tree structure
                current = current.right  # Move to right child
    return root
```

The time complexity of this solution is O(n) because we visit each node exactly once. The space complexity is O(1) since we are not using any additional data structures that depend on the size of the input; we only use a few pointers to keep track of the current node and its predecessor.

1. **Empty Tree**: If the input is an empty tree (root is None), the function should return None without any modifications.  
2. **Single Node Tree**: If the tree contains only one node, the function should double its value and return the modified node.  
3. **All Nodes in One Direction**: In cases where the tree is skewed (all nodes are either left or right), the algorithm should still correctly modify the values while maintaining O(1) space.

Optimize traversal for in-place

Zscaler

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

Zscaler 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