Tree Traversals.md

Tree Traversals

Interviewer Prompt

Today you will write a couple of functions to implement Breadth First Search and Depth First Search tree traversals. IMPORTANT NOTE: The tree will NOT necessarily be a Binary Tree.

• breadthFirst
• depthFirstPreOrder

(If time allows, have your interviewee implement DFS Post Order traversal)

• depthFirstPostOrder

Each of these functions will take the root node of a tree as a parameter (the interviewee may use other parameters). Your functions should traverse the tree and "process" each node it visits. Your functions should return an array of all the values of the nodes in the order they were processed. Both functions will traverse the entire tree, but the order in which the nodes are processed depends on the function.

As a reminder:

• Breadth First Search traverses the tree level by level from left to right.
• Depth First Search traverses the tree one branch at a time.
  • DFS Pre Order: Root == > Children in order from left to right
  • DFS Post Order: Children in order from left to right ==> Root

Setup

// notice how there is no concept of 
// "left" or "right" child here
// because, in this tree structure,
// each node can have more than two children

function node(value) {
  this.val = value
  this.children = []
}

var a = node('a');
var b = node('b');
var c = node('c');
var d = node('d');
var e = node('e');
var f = node('f');
var g = node('g');
var h = node('h');
var i = node('i');
var j = node('j');
var k = node('k');
var l = node('l');
var m = node('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);

Example

Algorithm	Order	Explanation
breadthFirst	A B C D E F G H I J K L M	Tree is traversed level by level from left to right
depthFirstPreOrder	A B E K L C F G H M D I J	Root node is processed BEFORE its children
depthFirstPostOrder	K L E B F G M H C I J D A	Root is processed AFTER its children

Interviewer Guide

RE

• This differs from the traversal we worked on in junior phase because each node may have any number of children. We are used to dealing with binary trees in which each node has at most two children.

• You may need to remind your interviewee of what the different types of traversals mean. Check above for some explanations.

• The interviewee does not need to write the "node" function, but should be aware of the structure of a node. You may provide them with the function definition of a node.

• Be sure to have your interviewee sketch an example tree and have them talk you through the different traversals to make sure they understand the different ways a tree can be traversed.

AC

• Push a recursive solution.

• Remind them that each child of a tree node is it's own tree (this should hint to the recursive approach).

• Remind them that Breadth First Search uses a queue and Depth First Search uses a stack.

TO

• If your interviewee finishes, ask them:
  • What is the Big O of the breadth first? Depth first?
  • Does your answer change if this becomes a binary search tree (max two children)?

Solution Code (Breadth First)

const breadthFirst = rootNode => {

  // Breath First Search uses a queue to traverse a tree.
  // we progressively take nodes out of the queue to process
  // and then add the current node's children to the queue 
  // to be processed on a future iteration 
  
  const nodeQueue = [rootNode];
  
  // array to store processed nodes
  const processedNodes = []
  
  // pointer to current node
  let currNode
  
  while (nodeQueue.length) {
  
    // grab element in front of queue (FIFO)
    currNode = nodeQueue.shift();
    
    // "process" the current node
    processedNodes.push(currNode.val)
    
    // add the current node's children to 
    // the queue for the next iteration
    nodeQueue.push(...currNode.children);
  }
  
  return processedNodes
};

// Time complexity: O(n * m) where n is the number of nodes in tree 
// and m is the number of children of the node with the most children

// Space complexity: O(n) where n is the number of nodes in the tree

Solution Code (Depth First)

const depthFirstPreOrder = (rootNode, processedNodes = []) => {

  // Depth First Search uses a stack to traverse a tree.
  // in this implementation we are using the call stack,
  // but we can also solve the problem iteratively
  // and use a stack that we create ourselves (just a plain old array)

  // since we are doing PRE order, process our 
  // current node first
  processedNodes.push(rootNode.val)
  
  // if our current node has any children
  // process each one
  rootNode.children.forEach(child => {
    depthFirstPreOrder(child, processedNodes);
  });
  
  return processedNodes
};

const depthFirstPostOrder = (rootNode, processedNodes = []) => {

  // same as above except we will process our 
  // current node after we process it's children

  // process current node's children first
  rootNode.children.forEach(child => {
    depthFirstPostOrder(child, processedNodes);
  });
  
  // process our current node AFTER all it's children
  processedNodes.push(rootNode.val)
  
  return processedNodes
};

// (Time and space complexity is the same for all DFS traversals)

// Time complexity: O(n * m) where n is the number of nodes in tree 
// and m is the number of children of the node with the most children

// Space complexity: O(n) where n is the depth of the callstack (same as the number of nodes in this case)

/*
NOTE: 

For binary trees, the time complexity for Breadth First and Depth First Search drops to O(n) 
where n is the number of nodes in the tree. This is because, since binary tree nodes have at most two children, 
we don't have to iterate through each nodes children to add them to the queue. 
On each iteration, we will be pushing at most two children into the queue. 
Furthermore, we always have direct access to the children of nodes in a binary tree 
through their `left` and `right` properties. 
*/

Extra resources

Video Solution
BFS & DFS in-depth explanations
Repl with code above