0
\$\begingroup\$

Can the performance of the iterative approach be improved? I find that this approach lags behind many recursive options. no recursive answers, please.

Baseline recursive approach: takes 52 steps for this sized tree O(N) for every nested input each object is only touched once.

function diameterOfBinaryTree(root) {
  return diameterInternal(root).diameter;
};

function diameterInternal(root) {
  if (root == null) {
    return {
      diameter: 0,
      depth: 0
    }
  }
  let left = diameterInternal(root.left);
  let right = diameterInternal(root.right);
  let diameter = left.depth + right.depth;
  return {
    diameter: Math.max(diameter, left.diameter, right.diameter),
    depth: Math.max(left.depth, right.depth) + 1
  };
}

let tree = {
  "val": 3,
  "right": {
    "val": 20,
    "right": {
      "val": 7,
      "right": null,
      "left": null
    },
    "left": {
      "val": 15,
      "right": null,
      "left": null
    }
  },
  "left": {
    "val": 9,
    "right": null,
    "left": null
  }
}

console.log(diameterOfBinaryTree(tree))

Iterative approach: takes 85 steps. However, the number of steps will double as the branches become more nested. That's because as you walk the nodes, they are walked in trios. Counting the roots while unpacking the right and left side. Culminating the counts on every retrograde unpacking, while passing every root object more than once. time complexity is O(N^2) for every nested object added it will be touched twice, once on entering and a second time on exiting.

function diameterOfBinaryTree(root) {
  let stack = [
    [1, root]
  ];
  let d = new WeakMap()
  let diameter = 0;
  while (stack.length) {
    let [indicator, node] = [...stack.pop()];
    if (indicator) {
      let place = 0,
        extend = [];
      extend[place++] = [0, node]
      if (node.right !== null) {
        extend[place++] = [1, node.right]
      }
      if (node.left !== null) {
        extend[place++] = [1, node.left]
      }
      stack.push.apply(stack, extend);
    } else {
      let left = d.get(node.left) + 1 || 0;
      let right = d.get(node.right) + 1 || 0;
      d.set(node, Math.max(left, right))
      diameter = Math.max(diameter, left + right);
    }
  }
  return diameter;
}

let tree = {
  "val": 3,
  "right": {
    "val": 20,
    "right": {
      "val": 7,
      "right": null,
      "left": null
    },
    "left": {
      "val": 15,
      "right": null,
      "left": null
    }
  },
  "left": {
    "val": 9,
    "right": null,
    "left": null
  }
}

console.log(diameterOfBinaryTree(tree))

\$\endgroup\$
  • \$\begingroup\$ "Lags behind in many recursive options" in what way? Algorithmic complexity (what is the complexity of your implementation?)? Benchmarked runtime (can you demonstrate?)? Which implementations? \$\endgroup\$ – Bailey Parker Aug 22 '18 at 5:05
  • \$\begingroup\$ @BaileyParker sure this iterative approach will generate extra unnecessary null in the stack on every iteration. That compounds on deeply nested branches. Recursion can avoid generating those extra nulls. \$\endgroup\$ – Rick Aug 22 '18 at 6:21
  • \$\begingroup\$ "I find that this approach lags behind many recursive options." - Rule #1 when declaring code is slow is to show the numbers, it and another implementation as baseline. Saying code is slow because it "looks" slow doesn't count as slow. \$\endgroup\$ – Joseph Aug 23 '18 at 13:09
  • \$\begingroup\$ @joseph updated with a baseline recursive function. \$\endgroup\$ – Rick Aug 23 '18 at 17:32
2
\$\begingroup\$

Tail calls

You have to be careful when evaluating recursive functions as there is a big difference between recursion that is tail called, and those that are not.

As the problem requires a traverse back up the tree after locating an end node the tail of the recursive function should count as an iteration.

The upward traverse

The solution to the problem requires you to traverse down the nodes until you find the end node, counting the depth as you go. When you find an end node you then traverse back until you find a node with an un-traversed node. Each step back you record the max depth from that node.

Because the non iterative version requires you to push the current node to the stack so you can travel back up the tree you are counting what the recursive function is doing after the recursion (the tail).

Basics of tail calls

A tail call is a call made at the end of a function.

Many languages allow proper tail calls, which means that a tail called function does not need to push its current state to the call stack when it makes the recursive call, and thus there is no need to pop from the call stack when returning.

Consider the following two recursive functions.

Proper tail call recursion

function recurse(sum, value){
    sum += value;
    if(value > 10) { return sum }   // Returns functions state.sum
    return recurse(sum, value + 1); // Returns function call result
    // the functions state is not required after the recurse call.
}

console.log(recurse(0,0));

Non tail call recursion

function recurse(sum, value){
    if(value > 10) { return sum + value }  
    sum +=  recurse(value, value + 1); // Note that the function state
                                       // that holds sum must be retained
                                       // in order to complete the function
    return sum;  // Return function state variable
}

console.log(recurse(0,0));

The two functions return the same result, but the second function requires an additional 10 pops from the call stack.

Javaascript ES6 currently does support proper tail calls and optimization, however no engine has yet released support (too many pages rely on call stack overflow to save them from infinite recursion)

Do call stack pops count?

I do not know what the official stance is on the complexity of recursive tails. Having proper tail calls make a huge performance difference and some types of problems can not be implemented using proper tail calls so I would count them as iterations.

If you count the tail call (the pop from the call stack) as an iteration then your recursive function has the same number of iterations as the non recursive function.

As far as i can tell the solution can not be implemented using proper tail call recursion and thus the complexity should include both sides of the recursion call to be counted as an iteration.

var count = 0;
const nullReturn = {diameter: 0, depth: 0};
function diameterOfBinaryTreeA(root) {
  count = 0;
  const diameter = diameterInternal(root).diameter;
  console.log("Iterations : " + count);
  return diameter;
};

function diameterInternal(node) {
  count += 1;
  const left = node.left ? diameterInternal(node.left) : nullReturn;
  const right = node.right ? diameterInternal(node.right) : nullReturn;
  count += 1;
  const diameter = left.depth + right.depth;
  return {
    diameter: Math.max(diameter, left.diameter, right.diameter),
    depth: Math.max(left.depth, right.depth) + 1
  };
}



function diameterOfBinaryTreeB(root) {
  count = 0;
  const stack = [[1, root]];
  const nodeDepth = new WeakMap();
  let diameter = 0;
  while (stack.length) {
    count += 1;
    const [indicator, node] = stack.pop();
    if (indicator) {
      stack.push([0, node]);
      if (node.right) { stack.push([1, node.right]) }
      if (node.left) { stack.push([1, node.left]) }
    } else {
      const left = nodeDepth.get(node.left) + 1 || 0;
      const right = nodeDepth.get(node.right) + 1 || 0;
      nodeDepth.set(node, Math.max(left, right));
      diameter = Math.max(diameter, left + right);
    }
  }
  console.log("Iterations : " + count);
  return diameter;
}

let tree = {
  val: 3,
  right: {
    val: 20,
    right: {
      val: 7,
      right: null,
      left: null
    },
    left: {
      val: 15,
      right: null,
      left: null
    }
  },
  left: {
    val: 9,
    right: null,
    left: null
  }
}

console.log("Using recursion");
console.log("Diameter : " + diameterOfBinaryTreeA(tree))
console.log("Using Stack");
console.log("Diameter : " + diameterOfBinaryTreeB(tree))

Additional notes.

See above snippet for fixes as to the points below.

  • Use const for constants. You had many variables that were not being changes as let
  • When using recursive functions terminate the recursion before that call. If you have a recursive function and the first thing you do is check for a immediate return you are wasting a whole stack push and pop.
  • Don't forget to put ; at the end of lines.
  • Only use strings for property names if they are not valid names.
  • Keeping the extend array and place are not needed, just push the nodes directly to the stack.
  • if (node.left !== null) { is noisy if you know foo is either an object or null use if (node.left) {
  • Try to avoid non descriptive names, or use common abbreviations. d is not a good name for the map.
\$\endgroup\$

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.