šŸ”— LeetCode

Invert Binary Tree

EasydfsGoogleMeta

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

    šŸ’” Hints

    Hint 1

    Swap left and right children recursively.

    Algorithm Complexity

    Official asymptotic Big-O runtime and auxiliary memory analysis

    Linear
    Algorithmic Approach

    DFS to swap children.

    Time ComplexityO(N)
    Why:

    Each node in the binary tree is visited exactly once to swap its left and right child pointers.

    Space ComplexityO(H)
    Why:

    Recursion call stack uses memory proportional to the tree height H, bounded by O(log N) for balanced trees and O(N) worst-case.

    Big-O Growth CurveLinear (O(N))
    Execution time scales directly in proportion to the input size.

    šŸ” Dry Run

    Solutionā± O(N) | šŸ’¾ O(H)
    curr
    root
    4
    2
    1
    3
    7
    6
    9