LeetCode 156: Binary Tree Upside Down Solution

Master LeetCode problem 156 (Binary Tree Upside Down), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

156. Binary Tree Upside Down

Medium

Tree Depth-First Search Binary Tree

Problem Explanation

Explanation:

The problem asks us to flip a binary tree upside down. The idea is to perform a bottom-up traversal of the tree and modify the nodes accordingly. At each step, we set the right child of the current node as the left child of the next node and the left child of the current node as the right child of the next node. We continue this process until we reach the leftmost node, which becomes the new root of the upside-down tree.

Algorithm:

If the root is null or it has no left child, return the root.
Recursively traverse to the leftmost node (newRoot) by calling the function on the left child.
Set the left child of the leftmost node (newRoot) to the right child of the root.
Set the right child of the leftmost node (newRoot) to the root.
Set the left and right child of the root as null.
Return the newRoot as the root of the upside-down tree.

Time Complexity:

The time complexity of this approach is O(n) where n is the number of nodes in the binary tree.

Space Complexity:

The space complexity is O(h) where h is the height of the binary tree, due to the recursive calls on the stack.

: :

Solution Code

class Solution {
    public TreeNode upsideDownBinaryTree(TreeNode root) {
        if (root == null || root.left == null) {
            return root;
        }
        
        TreeNode newRoot = upsideDownBinaryTree(root.left);
        
        root.left.left = root.right;
        root.left.right = root;
        root.left = null;
        root.right = null;
        
        return newRoot;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 156 (Binary Tree Upside Down)?

This page provides optimized solutions for LeetCode problem 156 (Binary Tree Upside Down) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 156 (Binary Tree Upside Down)?

The time complexity for LeetCode 156 (Binary Tree Upside Down) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 156 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 156 in Java, C++, or Python.

Back to LeetCode Solutions