I was doing an algorithm problem and I came across this problem where you solve the sum of the node-depths (distance between a node in a BST and the tree's root).
I was confused about where they de-structure node and depth from stack.pop().
What is the purpose of this? And why is that iterating +1 on depth per loop?
function nodeDepths(root) {
console.log("root", root);
let depthSum = 0;
const stack = [{ node: root, depth: 0 }];
while (stack.length > 0) {
const { node, depth } = stack.pop();
console.log("node,", node, "depth", depth);
if (node === null) continue;
depthSum += depth;
stack.push({ node: node.left, depth: depth + 1 });
stack.push({ node: node.right, depth: depth + 1 });
}
return depthSum;
}
I was confused where they de-structure node and depth from stack.pop(); What is the purpose of this?
The while loop needs both the node and the depth properties, and those have been combined into an object which was pushed to the stack.
const { node, depth } = stack.pop();
if (node === null) continue;
// node--^ v---------depth
depthSum += depth;
stack.push({ node: node.left, depth: depth + 1 });
// / \
// node----------------+ +----- depth
// \ /
stack.push({ node: node.right, depth: depth + 1 });
And why are that iterating +1 on depth per loop?
The children are one level deeper than their parent, so we add one.
A simpler recursive version of this function is certainly possible, one where you don't have to maintain a stack:
const depthSum = (node, depth = 0) =>
node == null
? 0
: depth + depthSum (node .left, depth + 1) + depthSum (node .right, depth + 1)
const tree = { // Depth
value: 'a', // 0
left: {
value: 'b', // 1
left: {
value: 'c' // 2
},
right: {
value: 'd', // 2
left: {
value: 'e', // 3
right: {
value: 'f' // 4
}
}
}
},
right: {
value: 'g', // 1
left: {
value: 'h' // 2
},
right: {
value: 'i' // 2
} // +___
} // 17
}
console .log (depthSum (tree))This code is simpler and more direct. But it is less efficient and, depending upon the depth of your tree, could run into recursion depth limitations. The original is not subject to that. You would need to make the call for your own uses.