Problem Description

Given the root of a binary tree where all the right nodes are either leaf nodes with a sibling (a left node that shares the same parent) or empty, flip the tree upside down and return the new root.

In the upside-down version of the binary tree:

• The original left child becomes the new root.
• The original root becomes the new right child.
• The original right child becomes the new left child.

The transformation should be done in-place, and you must not create new nodes or reuse values. There is exactly one valid solution for each input tree.

Thought Process

At first glance, the problem seems to ask for a "rotation" of the binary tree, but it is more specific: for each subtree, the leftmost node becomes the new root, and each parent moves down to the right. The right child of any node becomes the left child of its parent in the new tree.

A brute-force approach would involve traversing the tree, collecting nodes, and reconstructing a new tree. However, the constraints require us to do this in-place, without creating new nodes.

To optimize, we notice that we can process the tree recursively (or iteratively), always focusing on the leftmost path. As we return from recursion, we rewire pointers, making the original parent the new right child and the original right child the new left child at each step.

Solution Approach

The solution can be implemented either recursively or iteratively. The recursive approach is more intuitive, as it naturally follows the leftmost path down to the new root, then rewires pointers as the call stack unwinds.

1. Base Case: If the current node is null or has no left child, it becomes the new root.
2. Recursive Case: Recursively call the function on the left child to reach the leftmost node.
3. Rewire Pointers:
   • The left child's left pointer should point to the original right child.
   • The left child's right pointer should point to the original node (parent).
4. Nullify Old Pointers: Set the original node's left and right pointers to null to avoid cycles.
5. Return the New Root: The result of the recursive call is the new root of the upside-down tree.

The iterative approach follows a similar logic, but uses a loop to traverse down the leftmost path, rewiring pointers at each step.

Example Walkthrough

Consider the following binary tree:

        1
       / \
      2   3
     / \
    4   5
  

Let's walk through the process:

1. Recursively move to the leftmost node (node 4). Since it has no left child, it becomes the new root.
2. Back at node 2:
   • Node 4's left pointer is set to node 5 (the right child of node 2).
   • Node 4's right pointer is set to node 2 (the parent).
3. Back at node 1:
   • Node 2's left pointer is set to node 3 (the right child of node 1).
   • Node 2's right pointer is set to node 1 (the parent).
4. Set the left and right pointers of nodes 1 and 2 to null.

        4
       / \
      5   2
          / \
         3   1
  

Time and Space Complexity

• Brute-force approach:
  • Time Complexity: O(N) to traverse all nodes and O(N) to reconstruct the tree, so O(N) overall.
  • Space Complexity: O(N) for storing nodes and constructing a new tree.
• Optimized (recursive/iterative) approach:
  • Time Complexity: O(N), since each node is visited and rewired exactly once.
  • Space Complexity: O(H), where H is the height of the tree, due to the recursion stack (or O(1) for iterative version).

The optimized approach is efficient and meets the problem's in-place constraint.

Summary

The "Binary Tree Upside Down" problem requires flipping a binary tree so the leftmost node becomes the new root, and the parent and right child are repositioned as right and left children, respectively. The in-place recursive (or iterative) solution elegantly walks down the leftmost path, rewires pointers as it unwinds, and meets both time and space efficiency requirements. This approach leverages the structure of the tree and pointer manipulation, making it both efficient and intuitive once understood.

Code Implementation

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def upsideDownBinaryTree(self, root: TreeNode) -> TreeNode:
        if not root or not root.left:
            return root
        newRoot = self.upsideDownBinaryTree(root.left)
        root.left.left = root.right
        root.left.right = root
        root.left = None
        root.right = None
        return newRoot
      

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    TreeNode* upsideDownBinaryTree(TreeNode* root) {
        if (!root || !root->left) return root;
        TreeNode* newRoot = upsideDownBinaryTree(root->left);
        root->left->left = root->right;
        root->left->right = root;
        root->left = nullptr;
        root->right = nullptr;
        return newRoot;
    }
};
      

// Definition for a binary tree node.
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

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;
    }
}
      

// Definition for a binary tree node.
function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
}

var upsideDownBinaryTree = function(root) {
    if (!root || !root.left) return root;
    let newRoot = upsideDownBinaryTree(root.left);
    root.left.left = root.right;
    root.left.right = root;
    root.left = null;
    root.right = null;
    return newRoot;
};