Recursive Traversal

Recursive traversal is clean and intuitive:

function preorder(node):
    if node == null: return
    process(node.val)
    preorder(node.left)
    preorder(node.right)

function inorder(node):
    if node == null: return
    inorder(node.left)
    process(node.val)
    inorder(node.right)

function postorder(node):
    if node == null: return
    postorder(node.left)
    postorder(node.right)
    process(node.val)

Time complexity: $O(n)$. Each node is visited exactly once.

Space complexity: $O(h)$ for the call stack, where $h$ is tree height.

In the worst case (skewed tree), $h = n$, so space is $O(n)$. For balanced trees, space is $O(\log n)$.