I am new to data structures in JavaScript and am trying to learn Binary Search Trees. I was following along with a blog post and was able to get a working solution to the problem of finding the max depth in a BST, but it’s unclear to me how the recursion is working and how the +1 gets added on each time at each level of depth. What is a good way to think about this? Is it basically that each time the nodes value is not null, 1 gets added to what will eventually be returned up the call stack (i.e. at each level as it backtracks up to the root)?
function maxDepth(node) { // console.log(node.left); if (node) { return Math.max(maxDepth(node.left), maxDepth(node.right)) + 1; } else { return 0; } }
Advertisement
Answer
The code for maxDepth(node)
reads like this:
If
node
is notnull
:- Run this same algorithm
maxDepth
onnode
‘s left child. Let this answer bex
. - Run this same algorithm
maxDepth
onnode
‘s right child. Let this answer bey
. - Calculate
Math.max(x, y) + 1
, and return this value as the answer for this function call.
- Run this same algorithm
Otherwise
node
isnull
, then return0
.
This means when we try to compute maxDepth(node)
on a non-null node, we first compute maxDepth()
on both of node
‘s children, and let those two subcomputations finish. Then we take the maximum of these values, add 1, and return the result.
Example:
a / b f / c e g / d
Call stack:
a => max(b,f) b => max(c,e) c => max(d,null) d => max(null,null) d <= (0,0)+1 = 1 c <= (1,0)+1 = 2 e => max(null,null) e <= (0,0)+1 = 1 b <= (2,1)+1 = 3 f => (null,g) g => (null,null) g <= (0,0)+1 = 1 f <= (0,1)+1 = 2 a <= (3,2)+1 = 4