6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ @OliverRadini I do not understand, the original answer is already recursive? \$\endgroup\$ – Koray Tugay Aug 6 at 10:48
  • \$\begingroup\$ Sorry, my mistake! \$\endgroup\$ – OliverRadini Aug 6 at 10:57
6
\$\begingroup\$

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;
};
\$\endgroup\$
  • \$\begingroup\$ Great minds think alike :D \$\endgroup\$ – Mohrn Aug 5 at 21:19
  • \$\begingroup\$ When do you attach a property to an object in JavaScript? In which cases? (The way I attach property depth for example..) \$\endgroup\$ – Koray Tugay Aug 5 at 22:00
  • \$\begingroup\$ 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. \$\endgroup\$ – ggorlen Aug 5 at 22:08
  • \$\begingroup\$ I see, thank you. Makes sense. \$\endgroup\$ – Koray Tugay Aug 5 at 22:09
  • \$\begingroup\$ No problem--check out side effect on wikipedia for more information on mutation. \$\endgroup\$ – ggorlen Aug 5 at 22:10
2
\$\begingroup\$
  • 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)

\$\endgroup\$
  • \$\begingroup\$ What do you mean fix return value? \$\endgroup\$ – Koray Tugay Aug 5 at 21:23
  • \$\begingroup\$ @KorayTugay I changed the return value of the method, but it should return the same thing as in your original code. \$\endgroup\$ – Mohrn Aug 5 at 21:34
  • \$\begingroup\$ I see, thank you. \$\endgroup\$ – Koray Tugay Aug 5 at 21:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.