Here are my own “key” observations, possibly incomplete, on **5** standard tree walk algos, based on my book [[discrete math]]

- pre/in/post-order is defined for
**binary** trees only. Why? in-order means “left-subtree, parent, right-subtree”, implying only 2 subtrees.
- In contrast, BFS/DFS are much more versatile. Their input can be any tree (binary etc) or other connected
**graphs**. If not a tree, then BFS/DFS will *produce* a tree — you first choose a “root” node arbitrarily.
- The 3 *-order walks are recursively defined. I believe they are
**three specializations of DFS**. See https://www.cs.bu.edu/teaching/c/tree/breadth-first/

—-That’s a tiny intro. Below are more advanced —

BFS uses an underlying queue. In contrast DFS is characterized by *backtracking*, which requires a *stack*. However, you can implement the queue/stack without recursion.

BFS feels like the most intuitive algo, recursion-free. Example — send a ~~mailer to all linkedin contacts:~~

# send to each direct contact

# send to each second-degree contacts …

DFS backtrack in my own language —

- # start at root.
- At each node, descend into first [1] subtree
- # descend until a leaf node A1
- # backtrack exactly one level up to B
- # descend into A1’s immediate next sibling A2’s family tree (if any) until a leaf node. If unable to move down (i.e. no A2), then move up to C.

Visually — if we assign a $val to each node such that these nodes form a BST, then we get the “shadow rule”. In-order DFS would probably visit the nodes in ascending order by $value

[1] the child nodes, of size 1 or higher, at each node must be remembered in some order.