Trees

LeetCode 226

LeetCode #226Difficulty: EasyNeetCode 150

LeetCode 226: Invert Binary Tree

LeetCode

Given the root of a binary tree, invert the tree, and return its root.

Problem Description

Given the root of a binary tree, invert the tree, and return its root.

Examples:
Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]
Constraints:
  • The number of nodes in the tree is in the range [0, 100].

Core Mental Model

At each node, swap left and right subtrees recursively. The post-order traversal swaps bottom-up.

Formal Loop Invariant

Invariant: After visiting node N, its left and right subtrees are completely inverted.

Key Architectural Takeaway:

Tree problems decompose cleanly into identical subproblems on left and right subtrees.

Asymptotic Complexity Analysis

Time ComplexityO(N)Linear scan
Space ComplexityO(H) call stack where H is tree height.Constant auxiliary

Bottleneck: Visits each node once.

Edge Cases & Screener Traps

  • Empty root null
  • Skewed linked-list tree