LeetCode 156 - Binary Tree Upside Down

LeetCode Problem 156

Difficulty: 🟡 Medium
Topics: Tree, Depth-First Search, Binary Tree

Solution

Problem Understanding

The problem asks us to transform a binary tree into its "upside-down" version. In more precise terms, we are given a binary tree where every right node either has a left sibling or is absent, and no right node has children. The transformation involves rotating the tree so that the leftmost path becomes the new root-to-leaf path. Specifically, for each node, the original left child becomes the new root, the original root becomes the new right child, and the original right child becomes the new left child.

The input is a TreeNode object representing the root of a binary tree. Each node has a val, left, and right pointer. The output should be the root of the transformed tree.

Key constraints are that the tree is small (0 to 10 nodes) and well-formed regarding the right node rules. The small input size suggests that recursion is practical and that performance is not a primary concern. Edge cases include empty trees, single-node trees, and trees where all nodes only have left children.

Approaches

A naive approach is to traverse the tree recursively, keep track of the path along the leftmost children, and rebuild a new tree from scratch using auxiliary data structures like lists. While correct, this approach requires additional memory proportional to the height of the tree and is less elegant.

The optimal approach leverages recursion directly on the tree, taking advantage of the tree structure itself to invert it in-place. The recursion goes down the leftmost path, and as the call stack unwinds, each node's children are reassigned according to the upside-down rules. This method is concise, intuitive once understood, and requires no extra data structures beyond the call stack.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Rebuild the tree from leftmost path, uses extra list or array
Optimal	O(n)	O(h)	Recursive in-place transformation, only call stack of height h

Algorithm Walkthrough

1. If the root is None or has no left child, return the root. This is the base case where the subtree is already at its new root.
2. Recursively call the function on the left child to reach the leftmost node, which will become the new root.
3. After recursion returns, the current node's left child is now the root of the inverted subtree. Reassign the left child's left pointer to the current node's right child. This places the original right child as the new left child.
4. Reassign the left child's right pointer to the current node itself. This makes the current node the new right child.
5. Set the current node's left and right pointers to None to avoid cycles.
6. Return the new root obtained from the recursive call.

Why it works: The recursion ensures that the leftmost node becomes the root, and as the stack unwinds, each parent is repositioned according to the upside-down rules. Each reassignment preserves the tree structure and avoids overwriting any nodes prematurely.

Python Solution

# 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: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root or not root.left:
            return root
        
        new_root = self.upsideDownBinaryTree(root.left)
        
        root.left.left = root.right  # original right becomes new left
        root.left.right = root       # original root becomes new right
        
        root.left = None
        root.right = None
        
        return new_root

This Python implementation follows the recursive algorithm exactly. The base case handles empty or leaf nodes, recursion finds the leftmost node, and pointer reassignment flips the tree while clearing old links.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func upsideDownBinaryTree(root *TreeNode) *TreeNode {
    if root == nil || root.Left == nil {
        return root
    }

    newRoot := upsideDownBinaryTree(root.Left)

    root.Left.Left = root.Right
    root.Left.Right = root

    root.Left = nil
    root.Right = nil

    return newRoot
}

In Go, we handle nil similarly to Python's None. The recursion and pointer reassignment logic is identical. Go's type system ensures root.Left exists before accessing its fields, matching the algorithm's base case.

Worked Examples

Example 1:

Input: [1,2,3,4,5]

Step-by-step transformation:

Step	Current Node	New Root	Reassignments
1	1	4	Recursive call down left path
2	2	4	2.left = 5, 2.right = 1
3	1	4	1.left = None, 1.right = None

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

Example 2:

Input: []

Recursion immediately returns None.

Output: []

Example 3:

Input: [1]

Single-node tree returns itself.

Output: [1]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each node is visited exactly once for reassignment.
Space	O(h)	Recursive call stack uses memory proportional to tree height h.

Since the tree has a maximum of 10 nodes, the recursion stack will be small.

Test Cases

# Basic functionality
assert Solution().upsideDownBinaryTree(None) is None  # empty tree
root = TreeNode(1)
assert Solution().upsideDownBinaryTree(root).val == 1  # single node
root = TreeNode(1, TreeNode(2), TreeNode(3))
new_root = Solution().upsideDownBinaryTree(root)
assert new_root.val == 2 and new_root.left.val == 3 and new_root.right.val == 1

# Provided examples
root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
new_root = Solution().upsideDownBinaryTree(root)
assert new_root.val == 4 and new_root.left.val == 5 and new_root.right.val == 2
assert new_root.right.left.val == 3 and new_root.right.right.val == 1

Test	Why
empty tree	validates base case handling of None
single node	validates that a tree with one node returns itself
small tree	checks correctness for minimal left and right children
example from problem	validates full upside-down transformation

Edge Cases

Empty Tree: An empty tree should return None. The implementation handles this in the base case by immediately returning root if it is None.

Single Node Tree: A tree with only one node should remain unchanged. The base case also covers nodes without a left child, preventing unnecessary reassignment.

Left-leaning Tree: If the tree has nodes only on the left, each node becomes the parent of the previous node as recursion unwinds. The recursive reassignment ensures no cycles occur because left and right pointers are cleared after being reassigned.

These cases ensure robustness across all guaranteed input structures and validate that no assumptions about the presence of right children are violated.