Problem

Given a binary tree, find the deepest node in the tree.
Example input:
    1
   / \
  2   3
     / \
    4   5
Example output:
5

Solution

// Solution:
// The optimal solution is to use a depth first search to traverse the tree.
// The depth first search will keep track of the current depth and the deepest node.
// The depth first search will return the deepest node.
// This solution is optimal because it only traverses the tree once.

function findDeepestNode(root) {
  let deepestNode = null;
  let deepestDepth = 0;

  function traverse(node, depth) {
    if (node === null) {
      return;
    }

    if (depth > deepestDepth) {
      deepestDepth = depth;
      deepestNode = node;
    }

    traverse(node.left, depth + 1);
    traverse(node.right, depth + 1);
  }

  traverse(root, 0);
  return deepestNode;
}