Binary Tree Upside Down

Problem

Given a binary tree where every right node is either a leaf or a sibling, flip the tree upside down. The leftmost leaf becomes the new root.

Key insight: Process iteratively or recursively. At each level: new_root = left child; new_root.left = right_sibling; new_root.right = parent.

Solutions

# Python — iterative
def upsideDownBinaryTree(root):
    cur, parent, right_sibling = root, None, None
    while cur:
        next_left = cur.left
        cur.left = right_sibling
        right_sibling = cur.right
        cur.right = parent
        parent = cur
        cur = next_left
    return parent

// C++
TreeNode* upsideDownBinaryTree(TreeNode* root) {
    TreeNode *cur = root, *par = nullptr, *right = nullptr;
    while (cur) {
        TreeNode* nextLeft = cur->left;
        cur->left = right;
        right = cur->right;
        cur->right = par;
        par = cur;
        cur = nextLeft;
    }
    return par;
}

// Java
public TreeNode upsideDownBinaryTree(TreeNode root) {
    TreeNode cur = root, par = null, right = null;
    while (cur != null) {
        TreeNode nextLeft = cur.left;
        cur.left = right;
        right = cur.right;
        cur.right = par;
        par = cur;
        cur = nextLeft;
    }
    return par;
}

// JavaScript
function upsideDownBinaryTree(root) {
    let cur = root, par = null, right = null;
    while (cur) {
        const nextLeft = cur.left;
        cur.left = right;
        right = cur.right;
        cur.right = par;
        par = cur;
        cur = nextLeft;
    }
    return par;
}

Complexity

Time: O(h)
Space: O(1)