⚡Flashcard Drill➔
NeetCode #471LC-156MediumTrees
← Back to All Problems

#471 · #156 · Binary Tree Upside Down(上下翻转二叉树)

📌 Problem Statement & Constraints

Given the root of a binary tree, turn it upside down: the original leftmost path becomes the new left spine, with each original left child becoming a parent whose right child is the original parent. Return the new root. Constraints: the number of nodes is in [0, 10]; every right node either has a sibling or no children.

💡 Core Algorithmic Approaches

  1. Recurse all the way down the left spine; the deepest left node becomes the new root.
  2. On the way back up, the current node's left child becomes its parent, and the current node becomes that parent's right child.
  3. The original right child of the current node becomes the new left child of the promoted node.
  4. This is a bottom-up relinking, which the recursion's return value makes natural.

💻 Benchmark Python3 Implementation

class Solution:
    def upsideDownBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        # the deepest left node becomes the new root
        if not root or not root.left:
            return root
        new_root = self.upsideDownBinaryTree(root.left)
        # promote root.left, attaching root and its old right child
        root.left.left = root.right        # old right child -> new left
        root.left.right = root             # old parent -> new right
        root.left = root.right = None      # the old parent becomes a leaf
        return new_root

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): each node on the left spine is visited once.
💾 Space Complexity
O(h) for the recursion stack, where h is the length of the left spine.

⚠️ Interview Pitfalls & Follow-ups

  • Returning root instead of new_root: the original root ends up deep in the new tree.
  • Forgetting to clear root.left and root.right: the old parent would keep stale children and create cycles.
  • Attaching root.right to the wrong slot: the original right child becomes the promoted node's left child.
  • Trying an iterative top-down approach: the relinking depends on the deepest node being known first, which the bottom-up recursion provides naturally.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Trees Problems