Recursive traversal is clean and intuitive:
def preorder(node):
if node == null: return
process(node.val)
preorder(node.left)
preorder(node.right)
def inorder(node):
if node == null: return
inorder(node.left)
process(node.val)
inorder(node.right)
def postorder(node):
if node == null: return
postorder(node.left)
postorder(node.right)
process(node.val)
Time complexity: —each node visited exactly once. Space complexity: for the call stack, where is tree height.
In the worst case (skewed tree), , so space is . For balanced trees, space is .