under engineered

Deepest node in binary tree

I came across today's Daily Coding Problem #622 and since it was tagged easy I thought of trying it out.

The problem was about finding the deepest node given a binary tree.

    a
   / \
  b   c
 /
d

Each node can be described to have a structure like this

type node = {
  val: some-value,
  left?: node,
  right?: node
}

The left and right values can be empty or null.

In the above example, it's clear by looking that the deepest node is d.

    a       0th level
   / \
  b   c     1st level
 /
d           2nd level

This can be solved by keeping track of the level as you traverse. In these cases one traverses recursively on each node till there are no children.

At each level you can check if the current level is greater than last traversed level. For this we'd need to store a variable to keep track of it.

I'll use a closure to save these as shown below.

const findDeepest = (root) => {
  let maxLevel = 0;
  let deepest = root;
  // what if this is the only node with no
  // children, so initialising it with argument

  const traverse = (node, level) => {
    // see if the level is greater
    // than `maxLevel` then save it
    // traverse right and left children
  };

  traverse(root, 0);
};

I've declared a traverse function which will basically do the heavy lifting. To start the recursive traversal I'm calling it given the current root and the current level which is 0 :P

Writing the traverse function

const traverse = (node, level) => {
  if (!node) return;

  if (level > maxLevel) {
    maxLevel = level;
    deepest = node;
  }

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

Notice how the traverse function recursively calls itself for the left subtree and the right subtree. We pass the level too by incrementing by 1 as the child is 1 level below the current node level.

Once it exhausts all possible subtrees then the value of maxLevel and deepest would be the answer.

We can just return these two once the function runs over.

Here's the final solution.

const findDeepest = (root) => {
  let maxLevel = 0;
  let deepest = root;
  // what if this is the only node with no
  // children, so initialising it with argument

  const traverse = (node, level) => {
    if (!node) return;

    if (level > maxLevel) {
      maxLevel = level;
      deepest = node;
    }

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

  traverse(root, 0);

  return deepest;
};

discuss on twitter, because why not?