Reacto for 9/19/18: Tree Traversal

treeTraversal.md

Tree Traversal

---

Instructions

Today you will write some different iterator functions for traversing trees:

1. breadthFirst

2. depthFirstPreOrder

3. depthFirstPostOrder

• Each of these functions will take a node of the tree and a callback. The function will iterate through the nodes, invoking the callback function on each of them.

• The difference between these functions is the order in which they iterate

• HELPFUL HINTS:

  • The 'callback' could be a function that does anything, but for the sake of simplicity, you can pretend it's console.log
  • Each node may have any number of children
  • Each child of a node is itself a tree (think recursively for depthfirst!)
  • Sketch out some example trees if you get stuck

---

Setup

function makeNode(val) {
  return {
    value: val,
    children: []
  }
}
const a = makeNode('a');
const b = makeNode('b');
const c = makeNode('c');
const d = makeNode('d');
const e = makeNode('e');
const f = makeNode('f');
const g = makeNode('g');
const h = makeNode('h');
const i = makeNode('i');
const j = makeNode('j');
const k = makeNode('k');
const l = makeNode('l');
const m = makeNode('m');

a.children.push(b,c,d);
b.children.push(e);
e.children.push(k,l);
c.children.push(f,g,h);
h.children.push(m);
d.children.push(i,j);

---

Visualization & Examples

Algorithm	Order	Explanation
breadthFirst	A B C D E F G H I J K L M	Each "level" of the tree is printed in order
depthFirstPreOrder	A B E K L C F G H M D I J	Children nodes are visited before sibling nodes
depthFirstPostOrder	K L E B F G M H C I J D A	A node is not traversed until all its children are reached

---

Solution Code (Breadth First)

const breadthFirst = (startingNode, callback) => {

  const queue = [startingNode]; //treat as a queue (FIFO)
  
  while (queue.length) {
    const node = queue.shift(); //removes + returns first element from an array
    callback(node.value) //get that value & do something with it
    queue.push(...node.children); //push back on that node's children 
    //in ES5: queue = queue.concat(node.children) --> queue would be var/let
  }
  
}

---

Solution Code (Depth First)

const depthFirstPreOrder = (startingNode, callback) => {

  callback(startingNode.value); //action to be executed for each value
  
  startingNode.children.forEach(child => {
    depthFirstPreOrder(child, callback); //recursively call the function for each child
  })
}



const depthFirstPostOrder = (startingNode, callback) => {

  startingNode.children.forEach(child => { //drills down to lowest child (node with no children)
    depthFirstPostOrder(child, callback);
  })
  
  callback(startingNode.value); //action to be executed for each value
}

---

Wrap-up

Big O

• What is the Big O of the breadth first? Depth first?
• Does this change if this becomes a binary search tree (max 2 children per node)?