Scale Engineer

Invert Binary Tree

Easy
#0214Time: O(n) where n is the number of nodes in the tree as we need to visit each node onceSpace: O(h) where h is the height of the tree due to the recursive call stack. In worst case (skewed tree) it can be O(n)2 companies
Algorithms
Depth-First SearchBreadth-First Search
Data structures
TreeBinary Tree
Companies
OracleOzon

Prompt

Given the root of a binary tree, invert the tree, and return its root.

 

Example 1:

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

Example 2:

Input: root = [2,1,3]
Output: [2,3,1]

Example 3:

Input: root = []
Output: []

 

Constraints:

  • The number of nodes in the tree is in the range [0, 100].
  • -100 <= Node.val <= 100

Approaches

2 approaches with complexity analysis and trade-offs.

We can solve this problem using a recursive approach where we swap the left and right children of each node recursively.

Algorithm

  1. Check if root is null, return null if true
  2. Store left child in temporary variable
  3. Assign right child to left child
  4. Assign temporary variable (original left child) to right child
  5. Recursively call invertTree on left child
  6. Recursively call invertTree on right child
  7. Return root

Walkthrough

The recursive approach works by traversing the binary tree and swapping the left and right children of each node. For each node:

  1. First check if the root is null, if yes return null
  2. Swap the left and right children of the current node
  3. Recursively invert the left subtree
  4. Recursively invert the right subtree
  5. Return the root node

Here's the implementation:

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) {        // Base case: if root is null, return null        if (root == null) {            return null;        }                // Swap the left and right children        TreeNode temp = root.left;        root.left = root.right;        root.right = temp;                // Recursively invert left and right subtrees        invertTree(root.left);        invertTree(root.right);                return root;    }}

Complexity

Time

O(n) where n is the number of nodes in the tree as we need to visit each node once

Space

O(h) where h is the height of the tree due to the recursive call stack. In worst case (skewed tree) it can be O(n)

Trade-offs

Pros

  • Simple and easy to understand

  • Clean and concise code

  • Uses less space compared to iterative approach

Cons

  • Can cause stack overflow for very deep trees

  • Recursive calls may have overhead

Solutions

/** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) { * this.val = val; * this.left = left; * this.right = right; * } * } */ public class Solution { public TreeNode InvertTree ( TreeNode root ) { if ( root == null ) { return null ; } TreeNode l = InvertTree ( root . left ); TreeNode r = InvertTree ( root . right ); root . left = r ; root . right = l ; return root ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem