Javascript - Find a deepest node in a binary tree

Question

Problem Statement

Given the root of a binary tree, return a deepest node.
For example, in the following tree, return d.
    a
   / \
  b   c
 /
d

My Implementation

module.exports = {
    deepestNode: function deepestNode(node, level) {
        if (!level)
            level = 0;

        node.depth = level;

        if (!node.left && !node.right)
            return node;

        let deepestLeft, deepestRight = node;

        if (node.left)
            deepestLeft = deepestNode(node.left, level + 1);

        if (node.right)
            deepestRight = deepestNode(node.right, level + 1);

        if (deepestLeft.depth > deepestRight.depth)
            return deepestLeft;
        else
            return deepestRight;
    },
    TreeNode: (val) => {
        return {
            val: val,
            left: null,
            right: null
        }
    }
};

Test Class

const expect = require('chai').expect;
const deepestNode = require('../../src/google/deepestNode');

let a = deepestNode.TreeNode('a');
let b = deepestNode.TreeNode('b');
let c = deepestNode.TreeNode('c');
let d = deepestNode.TreeNode('d');

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

expect(deepestNode.deepestNode(a).val).eq('d');

a = deepestNode.TreeNode('a');
expect(deepestNode.deepestNode(a).val).eq('a');

I am a Javascript newbie so any comments regarding either the algorithm itself or the use of Javascript is welcome.

Answer 1

Here are my thoughts:

• Don't mutate function parameters unless there is good reason to do so.

  node.depth = level;
  

  The above statement basically breaks the contract of the function. The function claims to locate the deepestNode, but in fact it does findDeepestNodeAndSetDeepestPropOnAllNodes (silly, but you get the idea). This could lead to confusing, subtle bugs for the client of your module and is a serious issue.

  If you want to return the level in addition to the node itself, that's easily done by returning a {node, level} object pair which doesn't corrupt the reference to node. However, since the test suite disregards the level, I'd omit it since the function name makes no mention of this and it's not typically valuable information.

• Always use braces for blocks of code:

  if (deepestLeft.depth > deepestRight.depth)
      return deepestLeft;
  else
      return deepestRight;
  

  is clearer and less error-prone as:

  if (deepestLeft.depth > deepestRight.depth) {
    return deepestLeft;
  }
  
  return deepestRight;
  

• Use default parameters:

  function deepestNode(node, level) {
      if (!level)
          level = 0;
  ...
  

  can be

  function deepestNode(node, level=0) {
  ...
  

• Avoid excessive conditionals; it's possible to simplify 6 branches to 2, reducing the cognitive load required to understand the code. Re-write negative conditionals to be positive when possible.

  For example,

  if (!node.left && !node.right)
      return node;
  

  can be eliminated. As a rule of thumb, I try to operate only on the current node when writing recursive functions unless I'm forced to do otherwise.

• Avoid excessive references and intermediate variables. Consider:

  let deepestLeft, deepestRight = node;
  /* ... various conditionals that may or may not change where
     `deepestLeft`, `deepestRight` and `node` points to ... */
  
  // later on, unclear state
  

  As with conditionals, when you begin relying on aliases for objects, it becomes difficult to keep track of what's pointing where. Code like this should only be written if there's no way around it, which isn't the case here.

  In fact, this line causes crashes when node.right is the only child of a node. You may have meant:

  let deepestLeft = deepestRight = node;
  

  Adding more thorough tests to your suite would help detect bugs like this.

  As an aside, prefer const instead of let unless you have to reassign the variable.

• Don't crash on undefined/null parameters if it's trivial to prevent.

  node.depth = level; // boom if `node` is undefined
  

---

Here's a re-write. I wrote this as browser code, but you can dump it into module.exports:

const deepestNode = (node, deepest={level: -1}, level=0) => {
  if (node) {
    if (level > deepest.level) {
      deepest.node = node;
      deepest.level = level;
    }

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

  return deepest.node;
};

class TreeNode {
  constructor(val, left=null, right=null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

const root = new TreeNode(1, 
  new TreeNode(2, 
    new TreeNode(4)
  ), 
  new TreeNode(3)
);

console.log(deepestNode(root));

This function can also be written iteratively in a clean way, avoiding call stack overflow errors and function call overhead:

const deepestNode = node => {
  let deepest = {level: -1};
  const stack = [[node, 0]];

  while (stack.length) {
    const [curr, level] = stack.pop();

    if (curr) {
      if (level > deepest.level) {
        deepest = {node: curr, level: level};
      }

      stack.push([curr.left, level + 1], [curr.right, level + 1]);
    }
  }

  return deepest.node;
};

Answer 2

• Use brackets for one-liner blocks (opinionated, but pretty strong consensus for this)
• Use shorthand object notation { val: val } -> { val }
• Use default value syntax
• Prefer const to let (this goes for your test too)
• Prefer ternary to if (not true if readability suffers)
• Let TreeNode take right and left as parameters

module.exports = {
  deepestNode(node) {
    const search = (node, depth = 0) => {
      const { left, right } = node;

      if (!left && !right) {
        return { node, depth };
      }

      const deepestLeft = left ? search(left, depth + 1) : { depth: -1 };
      const deepestRight = right ? search(right, depth + 1) : { depth: -1 };

      return deepestLeft.depth > deepestRight.depth
        ? deepestLeft
        : deepestRight;
    };
    return search(node).node;
  },
  TreeNode: (val, left = null, right = null) => ({
    val,
    left,
    right
  })
};

Update: fix return value. And typos...

Update 2: adjusted to @ggorlen point on not mutating the parameter

Update 3: fix return value (again)