ūüĎč
Welcome to my blog!

Node Depth

Unravel the intricacies of calculating node depth in data structures with this in-depth tutorial.

Node Depth
BT
easy

Published At

7/3/2021

Reading Time

~ 4 min read

The distance between a node in a Binary Tree and the tree's root is called the node's depth.

Write a function that takes in a Binary Tree and returns the sum of its nodes' depths.

Each BinaryTree node has an integer value, a left child node, and a right child node. Children nodes can either be BinaryTree nodes themselves or None / null.

Sample Input

jstree =    1
       /     \
      2       3
    /   \   /   \
   4     5 6     7
 /   \
8     9
jstree =    1
       /     \
      2       3
    /   \   /   \
   4     5 6     7
 /   \
8     9

Sample Output

js16
// The depth of the node with value 2 is 1.
// The depth of the node with value 3 is 1.
// The depth of the node with value 4 is 2.
// The depth of the node with value 5 is 2.
// Etc..
// Summing all of these depths yields 16.
js16
// The depth of the node with value 2 is 1.
// The depth of the node with value 3 is 1.
// The depth of the node with value 4 is 2.
// The depth of the node with value 5 is 2.
// Etc..
// Summing all of these depths yields 16.

Hints

Hint 1

As obvious as it may seem, to solve this question, you'll have to figure out how to compute the depth of any given node; once you know how to do that, you can compute all of the depths and add them up to obtain the desired output.

Hint 2

To compute the depth of a given node, you need information about its position in the tree. Can you pass this information down from the node's parent?

Hint 3

The depth of any node in the tree is equal to the depth of its parent node plus 1. By starting at the root node whose depth is 0, you can pass down to every node in the tree its respective depth, and you can implement the algorithm that does this and that sums up all of the depths either recursively or iteratively.

Optimal Space & Time Complexity

Average case: when the tree is balanced O(n) time | O(h) space - where n is the number of nodes in the Binary Tree and h is the height of the Binary Tree

Solution-1
jsfunction nodeDepths(root) {
  let sums = [];
	findNodeSums(root, 0, sums);
	
	let sum = sums.reduce((a,b) => a+b, 0);
	return sum
}
 
function findNodeSums(node, runningSum, sums) {
	if(!node) return;
	
	sums.push(runningSum);
	
	let newRunningSum = runningSum + 1;
	if(!node.left && !node.right) {
		return;
	}
	
	findNodeSums(node.left, newRunningSum, sums);
	findNodeSums(node.right, newRunningSum, sums);
}
 
// This is the class of the input binary tree.
class BinaryTree {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}
Solution-1
jsfunction nodeDepths(root) {
  let sums = [];
	findNodeSums(root, 0, sums);
	
	let sum = sums.reduce((a,b) => a+b, 0);
	return sum
}
 
function findNodeSums(node, runningSum, sums) {
	if(!node) return;
	
	sums.push(runningSum);
	
	let newRunningSum = runningSum + 1;
	if(!node.left && !node.right) {
		return;
	}
	
	findNodeSums(node.left, newRunningSum, sums);
	findNodeSums(node.right, newRunningSum, sums);
}
 
// This is the class of the input binary tree.
class BinaryTree {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}
Solution-2
jsfunction nodeDepths(root) {
  let sumOfDepth = 0;
	const stack = [{node: root, depth: 0}]
	while(stack.length > 0) {
		let {node, depth} = stack.pop();
		if (node == null) continue;
		sumOfDepth += depth;
		stack.push({node: node.left, depth: depth + 1});
		stack.push({node: node.right, depth: depth + 1});
	}
	return sumOfDepth
}
 
// This is the class of the input binary tree.
class BinaryTree {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}
Solution-2
jsfunction nodeDepths(root) {
  let sumOfDepth = 0;
	const stack = [{node: root, depth: 0}]
	while(stack.length > 0) {
		let {node, depth} = stack.pop();
		if (node == null) continue;
		sumOfDepth += depth;
		stack.push({node: node.left, depth: depth + 1});
		stack.push({node: node.right, depth: depth + 1});
	}
	return sumOfDepth
}
 
// This is the class of the input binary tree.
class BinaryTree {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}
Solution-3
jsfunction nodeDepths(root, depth = 0) {
  if (root === null) return 0;
	return depth + nodeDepths(root.left, depth + 1) + nodeDepths(root.right, depth + 1);
}
 
// This is the class of the input binary tree.
class BinaryTree {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}
Solution-3
jsfunction nodeDepths(root, depth = 0) {
  if (root === null) return 0;
	return depth + nodeDepths(root.left, depth + 1) + nodeDepths(root.right, depth + 1);
}
 
// This is the class of the input binary tree.
class BinaryTree {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

ūüē≥

Do you have any questions, or simply wish to contact me privately? Don't hesitate to shoot me a DM on Twitter.

Have a wonderful day.
Abhishek ūüôŹ

Join My Exclusive Newsletter Community

Step into a world where creativity intersects with technology. By subscribing, you'll get a front-row seat to my latest musings, full-stack development resources, and exclusive previews of future posts. Each email is a crafted experience that includes:

  • In-depth looks at my covert projects and musings to ignite your imagination.
  • Handpicked frontend development resources and current explorations, aimed at expanding your developer toolkit.
  • A monthly infusion of inspiration with my personal selection of quotes, books, and music.

Embrace the confluence of words and wonder, curated thoughtfully and sent straight to your inbox.

No fluff. Just the highest caliber of ideas.