Big O Practice: Invert Binary Tree

def invert_tree(node):
    if not node:
        return None
    left = invert_tree(node.right)
    right = invert_tree(node.left)
    node.left = left
    node.right = right
    return node

Variables

• n - number of nodes in the tree
• h - height of the tree

Explanation

Each node is visited once and has its children swapped - **O(n)** time. Auxiliary space is the recursion depth, **O(h)** - that is `O(log n)` for a balanced tree and `O(n)` for a degenerate one.

More Big O practice problems · Today's daily problem