Search⌘ K
AI Features
Home
Courses
Decode the Coding Interview in C#: Real-World Examples

Invert Binary Tree

Understand how to invert a binary tree by swapping left and right subtrees using depth-first search. This lesson helps you implement the solution efficiently and analyze its time and space complexity, strengthening your coding interview skills in tree data structures.

We'll cover the following...

Description

In this lesson, your task is to invert a given a binary tree, T.

Let’s look at an example below:

Coding exercise

Files
main.cs
TreeNode.cs
C#
using System;
using System.Collections.Generic;
class Solution {
    public static TreeNode invertTree(TreeNode root) {
        // write your code here
        return root;
    }
}

Solution

We can solve this problem using depth-first search (DFS).

The inverse of an empty tree is the empty tree. To invert tree T with root and subtrees left and right, we keep root the same and invert the right and left subtrees.

Let’s review the implementation below:

Files
main.cs
TreeNode.cs
C#
using System;
using System.Collections.Generic;
class Solution {
    public static TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return root;
        }
        TreeNode right = invertTree(root.right);
        TreeNode left = invertTree(root.left);
        root.left = right;
        root.right = left;
        return root;
    }
    public static void Main(){
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);
        Utility.print(invertTree(root));
    }
}
Invert binary tree

Complexity measures

Time Complexity Space Complexity
...