• 1

• 22.8k
• 2
• 16
• 40

#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.