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;
};

• Mohrn: Great minds think alike :D
• Koray Tugay: When do you attach a property to an object in JavaScript? In which cases? (The way I attach property depth for example..)
• ggorlen: If the function tells the client that it's going to permanently modify (mutate) the objects, then it's OK. For example, Array#push clearly modifies the object it's called on rather than returning a new copy. In your case, the function deepestNode is similar to Array#find in that it performs a search. You wouldn't want Array#find to mess with the objects it was supposed to search through, I'd guess.
• ggorlen: No problem--check out side effect on wikipedia for more information on mutation.
• Koray Tugay: Since we kind of moved away from a strict recursion and holding state in a variable, I think we do not need to pass the currentLevel to traverse. Something like this: pastebin.com/4k5N8vVw

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)

• Koray Tugay: What do you mean fix return value?
• Mohrn: @KorayTugay I changed the return value of the method, but it should return the same thing as in your original code.