Big O Practice: Balanced Bst Traversal

def in_order(node, out):
    if not node:
        return
    in_order(node.left, out)
    out.append(node.val)
    in_order(node.right, out)

def traverse(root):
    out = []
    in_order(root, out)
    return out

Variables

• n - number of nodes in the balanced tree

Explanation

Every node is visited once - **O(n)** time. The recursion stack grows with tree depth: for a **balanced** BST the depth is `log n`, so auxiliary space is **O(log n)**. For a degenerate (chain) tree it would be O(n) - the balanced assumption is the whole lesson here.

More Big O practice problems · Today's daily problem