5.21 Binary Tree Upside Down

5.21.1 Problem Metadata

• Platform: LeetCode
• Problem ID: 156
• Difficulty: Medium
• URL: https://leetcode.com/problems/binary-tree-upside-down/
• Tags:
• Techniques: Recursion, Tree

5.21.2 Description

Flip the tree so that every right child becomes a left sibling.

5.21.3 Solution - Recursive Rotation

5.21.3.1 Walkthrough

Recurse down the left spine to find the new root. On the way back, rotate pointers: set the left child’s left pointer to the current right child, and the left child’s right pointer to the current node. Null out the original children to avoid cycles.

5.21.3.2 Analysis

• Time Complexity: O(n)
• Space Complexity: O(h)

5.21.3.3 Code - Java

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