Tree Traversal
01 / The one-sentence essence
Every tree-traversal algorithm visits every node exactly once — the only thing that varies is when the visit happens relative to the recursive descent into children.
Problemtraverse a binary tree in a given orderTree[1, 2, 3, 4, 5, ·, 6]Modepreorder
output— nothing yet —
Depth-first — preorder visits the node before recursing into children.
step
0 / 7
visiting
—
visited
0 / 6
mode
preorder
0 / 7
02 / The pattern signature
# depth-first — three variants differ only in where "visit" sitstraverse(node):if node is null: returnvisit(node) // preordertraverse(node.left)visit(node) // inordertraverse(node.right)visit(node) // postorder# breadth-first — iterative, queue-basedlevel_order(root):q ← [root]while q not empty:node ← q.dequeue(); visit(node)enqueue node.left, node.right
03 / When to recognize this pattern
"in-order on a BST"
The sorted output of a binary search tree comes from inorder — that's a property of BSTs, not of inorder in general.
"level by level"
You need to process the tree row by row — node depths, zigzag output, "find the right side of the tree". Level-order via a queue is the tool.
"bottom-up / children-first"
You can't decide a node's answer until its children's answers are known — subtree sums, heights, paths. Postorder guarantees children are visited first.
"serialize / clone"
Producing a string representation of a tree, or copying one node-by-node. Often preorder with explicit null markers — it captures the structure unambiguously.
04 / Common pitfalls
Using inorder when postorder is required.
Anything that needs a child's answer to compute the parent's — subtree sums, heights, diameters — must visit children before the parent. That's postorder. Inorder will visit some children too late.
Forgetting the null check.
The first line of the recursive traversal is
if node is null: return. Missing it dereferences null at every leaf's missing children. The animation makes this explicit — null subtrees just don't render.Confusing the call stack with the output list.
The recursion's natural call stack is not the order of visits. A node is on the call stack from before its preorder visit through after its postorder visit — three different "moments" of the same node.
05 / Go practice — on LeetCode
easy21
01Binary Tree Inorder Traversal— LC 94→02Same Tree— LC 100→03Symmetric Tree— LC 101→04Maximum Depth of Binary Tree— LC 104→05Balanced Binary Tree— LC 110→06Minimum Depth of Binary Tree— LC 111→07Path Sum— LC 112→08Binary Tree Preorder Traversal— LC 144→09Binary Tree Postorder Traversal— LC 145→10Count Complete Tree Nodes— LC 222→11Invert Binary Tree— LC 226→12Binary Tree Paths— LC 257→13Sum of Left Leaves— LC 404→14Diameter of Binary Tree— LC 543→15Maximum Depth of N-ary Tree— LC 559→16Subtree of Another Tree— LC 572→17Merge Two Binary Trees— LC 617→18Search in a Binary Search Tree— LC 700→19Minimum Distance Between BST Nodes— LC 783→20Range Sum of BST— LC 938→21Cousins in Binary Tree— LC 993→
medium42
01Validate Binary Search Tree— LC 98→02Recover Binary Search Tree— LC 99→03Binary Tree Level Order Traversal— LC 102→04Binary Tree Zigzag Level Order Traversal— LC 103→05Construct Binary Tree from Preorder and Inorder Traversal— LC 105→06Construct Binary Tree from Inorder and Postorder Traversal— LC 106→07Binary Tree Level Order Traversal II— LC 107→08Path Sum II— LC 113→09Sum Root to Leaf Numbers— LC 129→10Binary Search Tree Iterator— LC 173→11Binary Tree Right Side View— LC 199→12Kth Smallest Element in a BST— LC 230→13Lowest Common Ancestor of a Binary Search Tree— LC 235→14Lowest Common Ancestor of a Binary Tree— LC 236→15Binary Tree Vertical Order Traversal— LC 314→16House Robber III— LC 337→17N-ary Tree Level Order Traversal— LC 429→18Path Sum III— LC 437→19Serialize and Deserialize BST— LC 449→20Delete Node in a BST— LC 450→21Convert BST to Greater Tree— LC 538→22Maximum Width of Binary Tree— LC 662→23Insert into a Binary Search Tree— LC 701→24Smallest Subtree with all the Deepest Nodes— LC 865→25Construct Binary Tree from Preorder and Postorder Traversal— LC 889→26Distribute Coins in Binary Tree— LC 979→27Smallest String Starting From Leaf— LC 988→28Construct Binary Search Tree from Preorder Traversal— LC 1008→29Binary Search Tree to Greater Sum Tree— LC 1038→30Lowest Common Ancestor of Deepest Leaves— LC 1123→31Tree Diameter— LC 1245→32Smallest Common Region— LC 1257→33Deepest Leaves Sum— LC 1302→34Maximum Product of Splitted Binary Tree— LC 1339→35Longest ZigZag Path in a Binary Tree— LC 1372→36Balance a Binary Search Tree— LC 1382→37Count Good Nodes in Binary Tree— LC 1448→38Diameter of N-Ary Tree— LC 1522→39Lowest Common Ancestor of a Binary Tree II— LC 1644→40Lowest Common Ancestor of a Binary Tree III— LC 1650→41Create Binary Tree From Descriptions— LC 2196→42Most Profitable Path in a Tree— LC 2467→