BFS^DFS, pre^in^post-order

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 —

  1. # start at root.
  2. At each node, descend into first [1] subtree
  3. # descend until a leaf node A1
  4. # backtrack exactly one level up to B
  5. # 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

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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s