Invert Binary Tree

What are binary trees?

• Hierarchical data structures with a single root node and each node having at most two children (left and right).

What does inverting a binary tree mean?

• Swapping the left and right subtrees of each node in the tree. The overall structure remains the same, but the positions of the subtrees are mirrored.

Why invert a binary tree?

• Primarily used as a practice problem for recursion and tree manipulation in computer science.
• In rare cases, it might be a building block for more complex tree algorithms or used for specific data organization needs (niche application).

How to invert a binary tree: (Two main approaches)

Recursive Approach:

• A function recursively swaps left and right subtrees at each node.
• Provided Java code demonstrates this approach.

Iterative Approach (Optional):

• Uses a stack to keep track of nodes, swapping children during processing.

Original Binary Tree:

Imagine a binary tree with the following structure (represented as a simple diagram):

      (5)
     /   \
    /     \
  (3)    (7)

• The root node has a value of 5.
• The left child has a value of 3.
• The right child has a value of 7.

Inverting the Tree:

Get Brijesh Srivastava’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

The process of inverting the tree involves swapping the left and right subtrees of each node. Here’s how it works:

1. Root Node (5):

• We start at the root node (5).
• Its left subtree (3) becomes its right subtree.
• Its right subtree (7) becomes its left subtree.

Updated diagram:

   (5)
  /   \  (swapped)
 (7)   (3)

2. Subtree Inversion (Recursive):

• Now, imagine we recursively perform the same swap operation on each of the subtrees (previously 3 and 7).
• This ensures the entire tree is eventually inverted.

Resulting Inverted Tree:

After swapping the subtrees throughout the tree, we get the inverted version:

      (5)
     /   \
    (7)   (3)

Explanation with Code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
      // If the tree is empty (null root), return null
        if(root == null) return root;
        invert(root);
        return root;
    }

    public void invert(TreeNode node){
        if(node == null) return;
        
      // Swap left and right subtrees of the current node
        TreeNode temp = node.left;
        node.left = node.right;
        node.right = temp;

      // Recursively invert the left and right subtrees
        invert(node.left);
        invert(node.right);
    }
}

The invert function swaps the left and right children using a temporary variable (temp).

The recursive calls (invert(root.left) and invert(root.right)) ensure the inversion propagates to all levels of the tree.

Recursive Approach:

• Time Complexity: O(n), where n is the number of nodes in the tree. This is because the invert function visits each node exactly once to swap its left and right subtrees.
• Space Complexity: O(n) in the worst case (skewed tree), O(log n) on average (balanced tree). In the worst case, the recursive calls create a call stack that can grow as deep as the height of the tree, which can be n in a skewed tree (all nodes have only one child). However, in a balanced tree, the height is logarithmic in relation to the number of nodes, leading to an average space complexity of O(log n).