Binary Tree Traversals

treehierarchicaltraversal

Press play to start

1function inOrder(node: TreeNode | null): void {
2  if (!node) return
3  inOrder(node.left)   // go left
4  // visit
5  console.log(node.value)
6  // go right
7  inOrder(node.right)
8}
9// Result: 4, 2, 5, 1, 6, 3, 7

Step 1/0

Complexity

Best:O(n)
Average:O(n)
Worst:O(n)
Space:O(h)

Description

Three ways to visit all nodes: in-order (left-root-right), pre-order (root-left-right), and post-order (left-right-root).

When to use

In-order gives sorted output for BST. Pre-order for copying/serializing trees. Post-order for deletion and evaluation.