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.
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.
The 3 *-order walks are recursively defined. I think they are subsets of DFS. See https://www.cs.bu.edu/teaching/c/tree/breadth-first/
BFS feels like the most intuitive algo, recursion-free. Example — send a
mailer to linkedin contacts.
# send to each direct contact
# send to each of my second-degree contacts …
DFS backtrack in my own language —
- # start at root.
- At each node, descend into first  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”. DFS would probably visit the nodes in ascending order by $value
 the child nodes, of size 1 or higher, at each node must be remembered in some order.