Binary Tree Upside Down

medium tree dfs binary tree

Problem

Given a binary tree where every right child has a sibling left child and no children of its own, flip it upside down. The leftmost leaf becomes the new root, the original right child becomes its left, and the original parent becomes its right.

Inputlevels = [1, 2, 3, 4, 5]

Output[4, 5, 2, null, null, 3, 1]

Node 4 is the leftmost leaf and becomes the new root; 5 → left, 2 → right; 3 hangs off 2 as left, 1 as right.

levels (left-skewed values, root → leaf, comma-separated)

right values per parent (one per parent in same order)

def upside_down_binary_tree(root):
    if root is None or root.left is None:
        return root
    new_root = upside_down_binary_tree(root.left)
    root.left.left = root.right
    root.left.right = root
    root.left = None
    root.right = None
    return new_root

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

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

TreeNode* upsideDownBinaryTree(TreeNode* root) {
    if (root == nullptr || root->left == nullptr) return root;
    TreeNode* newRoot = upsideDownBinaryTree(root->left);
    root->left->left = root->right;
    root->left->right = root;
    root->left = nullptr;
    root->right = nullptr;
    return newRoot;
}

Explanation

This tree only grows down its left spine, and flipping it amounts to making the leftmost leaf the new root and re-hanging every parent. Recursion handles this neatly by flipping the bottom first, then rewiring on the way back up.

The base case stops at the deepest node: when root.left is null, that node is the leftmost leaf and becomes the answer. We call upsideDownBinaryTree(root.left) first, and that call returns the new root unchanged all the way up.

After the recursive call returns, we rewire the current node. The original left child becomes the new parent, so root.left.left = root.right (the old right sibling becomes its left) and root.left.right = root (the old parent becomes its right). Then we clear root.left and root.right so the old node is now a leaf.

Example: spine 1 → 2 → 4 with rights 3 under 1 and 5 under 2. The deepest leaf 4 becomes root; 4.left = 5, 4.right = 2; then 2.left = 3, 2.right = 1.

Each node is rewired once, so the flip is O(n) time.

Time: O(n) Space: O(n) recursion