Tree Traversals (DFS)
DSA · Trees
Theory
Depth-first traversals visit nodes by going as deep as possible before backtracking. Pre-order visits root, left, right (useful for copying a tree). In-order visits left, root, right (gives sorted order in a BST). Post-order visits left, right, root (useful for deleting a tree or computing sizes bottom-up). Each visits every node once, so they take O(n) time and O(h) stack space for height h.
Why we use it
Traversals are how you read, search, copy, serialise and evaluate trees.
When to use it
Use pre-order to serialise or clone, in-order to get sorted output from a BST, post-order for bottom-up calculations such as folder sizes.
How it works
- visit(node)
- node is None? Yes: Return. No: Choose order.
- Preorder: node, left, right | Inorder: left, node, right | Postorder: left, right, node
- Recursion visits every node once: O(n)
Syntax
pre(n): visit(n); pre(n.left); pre(n.right)
in(n): in(n.left); visit(n); in(n.right)
post(n): post(n.left); post(n.right); visit(n)
Time: O(n) Space: O(h)Example
class Node:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
root = Node("F", Node("B", Node("A"), Node("D", Node("C"), Node("E"))), Node("G", None, Node("I", Node("H"))))
def pre(n, out):
if n:
out.append(n.val); pre(n.left, out); pre(n.right, out)
return out
def ino(n, out):
if n:
ino(n.left, out); out.append(n.val); ino(n.right, out)
return out
def post(n, out):
if n:
post(n.left, out); post(n.right, out); out.append(n.val)
return out
print("Pre-order: ", " ".join(pre(root, [])))
print("In-order: ", " ".join(ino(root, [])))
print("Post-order:", " ".join(post(root, [])))Key points
- Pre-order: root first
- In-order: sorted order for a BST
- Post-order: children before parent
- O(n) time, O(h) space