Deepest Binary Search Tree Node

Tree Traversal

Learning Objective

Apply recursion to BSTs, understand recursive structure of BSTs

Interviewer Prompt

Given a binary tree, write a function that will return the node in the tree with greatest depth.You may assume there is a unique deepest node.

Setup and Example

function node(val) {
  return {
    val,
    left: null,
    right: null
  };
}
let a = node('a');
let b = node('b');
let c = node('c');
let d = node('d');
let e = node('e');
let f = node('f');

a.left = b;
a.right = c;
b.right = d;
d.left = f;
c.left = e;

findDeepest(a) //Result: f

Interviewer Guide

RE

Interviewee does not need to write the "node" function, but should be aware of the structure of a node
Be sure to have your interviewee sketch an example tree
You may need to remind your interviewee of what depth means in a tree (the root has depth 0, and each node's depth is it's parent's depth + 1)

AC

You may want to remind your interviewee that many tree problems have a depth-first and a breadth-first solution
Remind them that each child of a tree node is it's own tree

TO

If your interviewee finishes, ask them:
What is the Big O of their approach?
If they found the depth first solution, suggest they look for a breadth first solution, or vice-versa

Solution Code (Depth First)

const findDeepestDFS = (node) => {
  let deepestNode = node
  let deepestLevel = 0
  // find is a helper function which we'll recurse over
  const find = (node, level = 0) => {
    if (node) {
      // if this node's level is deeper than the current "deepestLevel", replace it
      if (level > deepestLevel) {
        deepestNode = node;
        deepestLevel = level;
      }
      // recursive cases: if node.left and/or node.left exist, call the function on each, increasing the level by 1
      if (node.left) {
        find(node.left, level + 1);
      }
      if (node.right) {
        find(node.right, level + 1);
      }
      // the base case is implicit here: if there's no node.left or node.right, the function execution ends
    }
  }
  find(node)
  return deepestNode;
};

Solution Code (Breadth First)

const findDeepestBFS = (node) => {
  // we use a queue to iterate over the tree
  let queue = [node]
  let current;
  while (queue.length > 0) {
    current = queue.shift()
    if (current.left) queue.push(current.left)
    if (current.right) queue.push(current.right)
  }
  // when we exit the while loop, it means we've seen every node, in breadth-first order
  //current will be the last node we saw, which will necessarily be the deepest node in the tree
  return current;
}

sheppas/Deepest-BST-Node.md