deepest-bst-node.md

Tree Traversal 🌳

---

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

---

REACTO

• 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)

• 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

---

• If your interviewee finishes early and found the depth first solution, suggest they look for a breadth first solution, or vice-versa

---

Big O

In both solutions:

• Depth First: O(n)
• Breadth First: O(n)

Solution Code (Depth First)

const findDeepestDFS = (node) => {

  let deepestNode = node
  let deepestLevel = 0 //you can think of this as a counter 
  

  const find = (node, level = 0) => { //helper function; we will recursive over with the level set to the parent node as a default 
    if (node) {
      if (level > deepestLevel) { //this will be skipped the first run 
        deepestNode = node;
        deepestLevel = level;
      }
      // if node.left and/or node.left exist, call the recursive function, 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) => {
  // use a queue to iterate over the tree
  
  let queue = [node] // assigns the queue to an array with the node as an element
  let current;
  
  while (queue.length > 0) {
    current = queue.shift() // removes the node at the first index and assigns it as the current 
    if (current.left) queue.push(current.left) //checks if current node has any children on the left pushes that node on the to the queue 
    if (current.right) queue.push(current.right) //same for right side 
  }
  
  // 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, the deepest node in the tree
  
  return current;
}

---

💻 Repl: https://repl.it/@kyvyCodes/Deepest-BST-Node