Having a hard time visualizing the call order of binary tree recursion

Question

I am trying to visualize recursion for this particular problem solution below, and have placed 2 console.logs, but I still can’t understand it. The problem:

Node depths

Here is my solution. It works though I don't fully understand why.

function helper(root, depth) {
  console.log(depth, ‘step 1’)
  if(root === null) {
    console.log(depth, ‘step 2’)
    return 0;
  }

  if(root.left === null && root.right === null) {
    console.log(depth, ‘step 3’)
    return depth
  }

  console.log(depth, ‘step 4’)
  const leftSum = helper(root.left, depth + 1);
  const rightSum = helper(root.right, depth + 1);
   const totalSum = depth + leftSum + rightSum;
   return totalSum;
  
}

function nodeDepths(root) {
  return helper(root, 0);
}

In particular, for this input:

{
  "tree": {
    "nodes": [
      {"id": "1", "left": "2", "right": null, "value": 1},
      {"id": "2", "left": null, "right": null, "value": 2}
    ],
    "root": "1"
  }
}

For the case where depth is equal to 1 and node.value is 2, the algorithm order goes like below

0 step 1
0 step 4
1 step 1
1 step 3
1 step 1
1 step 2

My question is why at depth === 1, the code doesn’t go to step 4 after step 3 but goes back up to step 1 instead? And when a number is returned from the call stack, why is that number added to the sum of a branch (but not minus, multiply or divide)?

Thank you in advance! I’ve been stumped on this for the past 3 days.

I tried console.log out the callstack and expected it to go to step 4 after step 3 for when depth is equal to 1.

Answer 1

You recurse twice, in the code here:

const leftSum = helper(root.left, depth + 1);
const rightSum = helper(root.right, depth + 1);

The four lines that are prefixed with depth 1 combine the two calls, two lines from each.

The first call is on the left child of the root, which is a valid leaf node, so you see step 3 printed, since that's the base case for leaf nodes. The second recursion, on the right child, is running on a null value, and bails out in step 2, another base case.

It might help you better understand the recursion if you printed the root value, along with the depth.

As for why the depths are being added up, that I can't help you with. I just seems to be the task assigned in this exercise. I don't think there's any utility to that sum, unlike, for example, the maximum depth (which can be used to balance a tree, which helps make some algorithms more efficient).