Optimize inversion for without recursion

Question

Given a binary tree, write a function to invert the tree (swap the left and right children of all nodes) without using recursion. The function should take the root node of the tree as input and return the root of the inverted tree.

Codemia · Accepted Answer

The problem involves inverting a binary tree, which means swapping the left and right children of all nodes. This can be effectively approached using an iterative method, which is suitable given the constraint of not using recursion. The BFS (Breadth-First Search) pattern is ideal here because it allows us to traverse the tree level by level, processing each node and inverting it along the way. By utilizing a queue, we can maintain the nodes to be processed without the overhead of the call stack that recursion would introduce.

1. Begin by initializing a queue and enqueue the root node if it exists.
2. While the queue is not empty, perform the following:
   - Dequeue the front node.
   - Swap its left and right children.
   - If the left child is not null, enqueue it.
   - If the right child is not null, enqueue it.
3. Continue this process until all nodes have been processed and swapped.
4. Finally, return the root of the inverted tree.

**Example:** Given a binary tree represented as:
```
    1
   / \
  2   3
 / \  / \
4  5 6  7
```
After applying the inversion, it will become:
```
    1
   / \
  3   2
 / \  / \
7  6 5  4
```

Here is the Python code implementing the above approach:
```python
from collections import deque

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

def invertTree(root):
    if not root:
        return None
    queue = deque([root])
    while queue:
        current = queue.popleft()
        # Swap the children
        current.left, current.right = current.right, current.left
        
        # Enqueue the children
        if current.left:
            queue.append(current.left)
        if current.right:
            queue.append(current.right)
    return root
```

The time complexity of this solution is O(n), where n is the number of nodes in the tree, as we visit each node exactly once. The space complexity is also O(n) in the worst case due to the queue holding all nodes at the deepest level of the tree (which can happen in a completely unbalanced tree). In a balanced tree, the space complexity would be O(w), where w is the maximum width of the tree.

1. **Empty Tree:** If the root is None, the function should return None.
2. **Single Node Tree:** If the tree consists of only one node (the root), it should return the same node as swapping children has no effect.
3. **Linear Tree:** For a tree that is essentially a linked list (all nodes have only one child), the function should still correctly invert the pointers.
4. **Full Binary Tree:** Ensure that the function correctly handles a full binary tree where every node has either 0 or 2 children.

Optimize inversion for without recursion

Optiver

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

Optiver 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