# LeetCode: node-depths
Table of Contents
Statement
BST Representation
tree = 10 / \ 5 15 / \ / \ 2 5 13 22 / \ 1 14✅ Solution Explanation
To get the sum of all node depths, we traverse the entire tree. The root starts at depth 0, and every time we move down a level, the depth increases by 1. For each node, we add its depth to our total. This can be done either with recursion or with a stack in an iterative approach. In both cases, we visit every node once and accumulate their depths.
⏱️ Time Complexity
We must visit every node in the tree exactly one time to calculate its depth. Since no node is processed more than once, the total time is O(N), where N is the number of nodes.
💾 Space Complexity
The maximum extra space depends on the height of the tree (h):
Recursive solution: uses up to O(h) memory from the call stack.
Iterative solution: the stack also stores at most one node per level, so it is O(h) as well.
For a balanced tree, the height is about log(N). For a skewed tree, the height can be N in the worst case.
Iterative soluction
// 🌳 Binary Search Tree Nodeclass BST { constructor(value) { this.value = value this.left = null this.right = null }}
// 📌 Function to calculate the sum of node depthsfunction nodeDepths(root) { let sumOfDepths = 0; const stack = [{ node: root, depth: 0 }];
// 🔁 Keep looping while there are nodes in the stack while (stack.length > 0) { const nodeInfo = stack.pop(); const { node, depth } = nodeInfo;
if (node === null) continue;
sumOfDepths += depth;
// 👇 Push the children into the stack with depth + 1 stack.push({ node: node.left, depth: depth + 1 }); stack.push({ node: node.right, depth: depth + 1 }); }
return sumOfDepths; // ✅ Return the final result}
// 🌲 Build our treeconst root = new BST(10)root.left = new BST(5)root.right = new BST(15)
root.left.left = new BST(2)root.left.right = new BST(5)root.left.left.left = new BST(1)
root.right.left = new BST(13)root.right.right = new BST(22)root.right.left.right = new BST(14)
// 🚀 Run the functionconsole.log(nodeDepths(root)) // ✅ Output: 16recursive soluction
// 🌳 Binary Search Tree Nodeclass BST { constructor(value) { this.value = value this.left = null this.right = null }}
// 📌 Recursive function to calculate the sum of node depthsfunction nodeDepths(root, depth = 0) { if (root === null) return 0;
// 🧮 Add current depth + depths from left subtree + depths from right subtree return ( depth + nodeDepths(root.left, depth + 1) + nodeDepths(root.right, depth + 1) );}
// 🌲 Build our treeconst root = new BST(10)root.left = new BST(5)root.right = new BST(15)
root.left.left = new BST(2)root.left.right = new BST(5)root.left.left.left = new BST(1)
root.right.left = new BST(13)root.right.right = new BST(22)root.right.left.right = new BST(14)
// 🚀 Run the functionconsole.log(nodeDepths(root)) // ✅ Output: 16