Jobs

Interviews

Discussions

Invert Binary Tree

Easy

Oracle

0 views

Topics:

TreesRecursion

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

For example:

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

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

Input: root = []
Output: []

Constraints:

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

Could you provide an algorithm to invert the binary tree? Explain the time and space complexity. Can you handle edge cases, such as an empty tree?

Invert Binary Tree

Easy

Oracle

0 views

Topics:

TreesRecursion

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

For example:

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

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

Input: root = []
Output: []

Constraints:

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

Could you provide an algorithm to invert the binary tree? Explain the time and space complexity. Can you handle edge cases, such as an empty tree?

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the tree be empty, i.e., can `root` be null?
What is the data type of the values stored in the nodes of the tree? Can I assume it's integers?
Are the values in the nodes guaranteed to be unique, or can there be duplicates?
Is there a maximum depth or number of nodes the tree can have?
Should the inversion be done in-place, or is creating a new inverted tree allowed?

Brute Force Solution

Approach

The brute force approach to inverting a binary tree involves examining every single node. For each node, we simply swap its left and right children. This process ensures the entire tree is inverted by exhaustively considering each node's arrangement.

Here's how the algorithm would work step-by-step:

Start at the very top of the tree, at the root node.
For this top node, switch its left side with its right side.
Now, move down to the left side of the tree and do the same thing: switch the left and right sides of that node.
Next, move down to the right side of the tree from the top and switch the left and right sides of that node as well.
Continue this process, going down each side (left and right) of every node in the tree and switching their left and right children.
Keep doing this until you've reached the very bottom of the tree and switched the children of every single node.

Code Implementation

def invert_binary_tree(root): 
    if root: 
        # Swap the left and right children of the current node
        root.left, root.right = root.right, root.left

        # Recursively invert the left subtree
        invert_binary_tree(root.left)

        # Recursively invert the right subtree
        invert_binary_tree(root.right)

    return root

Big(O) Analysis

Time Complexity

O(n) – The algorithm visits each of the n nodes in the binary tree exactly once. At each node, it performs a constant-time operation: swapping the left and right children. Therefore, the time complexity is directly proportional to the number of nodes in the tree. This linear relationship results in a Big O time complexity of O(n), where n is the number of nodes.

Space Complexity

O(H) – The described algorithm uses recursion to traverse the binary tree. In the worst-case scenario, the recursion depth can be equal to the height (H) of the tree, where each level of recursion adds a new frame to the call stack. Each frame requires constant space, but the maximum number of frames on the stack corresponds to the tree's height. Therefore, the auxiliary space complexity is O(H), where H is the height of the tree.

Optimal Solution

Approach

To invert a binary tree, we want to swap the left and right children of every node in the tree. The process is recursive, meaning we'll apply the same logic to smaller parts of the tree until the entire tree is inverted. We essentially visit each node and swap its children.

Here's how the algorithm would work step-by-step:

Start at the very top of the tree (the root node).
For the current node, switch its left child with its right child.
Move down to the left child of the current node, and repeat the switching process on this child.
Move down to the right child of the current node, and repeat the switching process on this child.
Continue this process until you've reached the bottom of the tree where there are no more children to switch.
The entire tree will now be inverted, with the left and right subtrees mirrored.

Code Implementation

def invert_binary_tree(root):
    if root is None:
        return None

    # Swap the left and right children of the current node
    root.left, root.right = root.right, root.left

    # Recursively invert the left subtree
    invert_binary_tree(root.left)

    # Recursively invert the right subtree
    invert_binary_tree(root.right)

    return root

Big(O) Analysis

Time Complexity

O(n) – The algorithm visits each node in the binary tree exactly once. For each node visited, a constant amount of work is performed (swapping the left and right children). Therefore, the time complexity is directly proportional to the number of nodes in the tree, denoted as n. The total operations approximate to c * n, where c is constant, which simplifies to O(n).

Space Complexity

O(H) – The primary space usage comes from the recursion stack. In the worst-case scenario (a skewed tree), the recursion depth can reach N, where N is the number of nodes in the tree. However, for a balanced tree, the recursion depth will be log₂(N), represented as H (height of the tree). Thus, the auxiliary space complexity is determined by the maximum depth of the recursion stack, which is proportional to the height (H) of the binary tree being inverted.

Edge Cases

Case	How to Handle
Null or empty tree (root is null)	Return null immediately; an empty tree inverted is still an empty tree.
Tree with only one node (root with no children)	Return the root node itself as it is already considered inverted.
Completely unbalanced or skewed tree (all nodes on one side)	Recursive or iterative approaches should handle this without stack overflow given sufficient resources, but watch for very deep recursion.
Perfectly balanced tree	Standard recursive or iterative approaches should efficiently invert this type of tree.
Tree with duplicate values	The inversion process is based on structure, not data values, so duplicates have no impact.
Very large tree (potential stack overflow with recursion)	Consider an iterative approach using a stack or queue to avoid exceeding recursion depth limits.
Tree with negative values	The value of the nodes does not impact tree inversion; no special handling is required.
Root having only a left or right child.	The algorithm should still correctly swap the single child to the other side and continue the traversal.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the tree be empty, i.e., can `root` be null?
What is the data type of the values stored in the nodes of the tree? Can I assume it's integers?
Are the values in the nodes guaranteed to be unique, or can there be duplicates?
Is there a maximum depth or number of nodes the tree can have?
Should the inversion be done in-place, or is creating a new inverted tree allowed?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start at the very top of the tree, at the root node.
For this top node, switch its left side with its right side.
Now, move down to the left side of the tree and do the same thing: switch the left and right sides of that node.
Next, move down to the right side of the tree from the top and switch the left and right sides of that node as well.
Continue this process, going down each side (left and right) of every node in the tree and switching their left and right children.
Keep doing this until you've reached the very bottom of the tree and switched the children of every single node.

Code Implementation

def invert_binary_tree(root): 
    if root: 
        # Swap the left and right children of the current node
        root.left, root.right = root.right, root.left

        # Recursively invert the left subtree
        invert_binary_tree(root.left)

        # Recursively invert the right subtree
        invert_binary_tree(root.right)

    return root

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start at the very top of the tree (the root node).
For the current node, switch its left child with its right child.
Move down to the left child of the current node, and repeat the switching process on this child.
Move down to the right child of the current node, and repeat the switching process on this child.
Continue this process until you've reached the bottom of the tree where there are no more children to switch.
The entire tree will now be inverted, with the left and right subtrees mirrored.

Code Implementation

def invert_binary_tree(root):
    if root is None:
        return None

    # Swap the left and right children of the current node
    root.left, root.right = root.right, root.left

    # Recursively invert the left subtree
    invert_binary_tree(root.left)

    # Recursively invert the right subtree
    invert_binary_tree(root.right)

    return root

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty tree (root is null)	Return null immediately; an empty tree inverted is still an empty tree.
Tree with only one node (root with no children)	Return the root node itself as it is already considered inverted.
Completely unbalanced or skewed tree (all nodes on one side)	Recursive or iterative approaches should handle this without stack overflow given sufficient resources, but watch for very deep recursion.
Perfectly balanced tree	Standard recursive or iterative approaches should efficiently invert this type of tree.
Tree with duplicate values	The inversion process is based on structure, not data values, so duplicates have no impact.
Very large tree (potential stack overflow with recursion)	Consider an iterative approach using a stack or queue to avoid exceeding recursion depth limits.
Tree with negative values	The value of the nodes does not impact tree inversion; no special handling is required.
Root having only a left or right child.	The algorithm should still correctly swap the single child to the other side and continue the traversal.