Node Depth in Binary Tree — Competitive Programming with Time and Space Complexity

Question

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:

Tree is given as:

Binary Tree

Sample Output:

16

// 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.

Solution

private int GetDepth(BinaryTree tree, int depth)
{
if (tree == null) return 0;
return depth + GetDepth(tree.left, depth + 1) +
GetDepth(tree.right, depth + 1);
}
private int NodeDepth(BinaryTree tree, int depth, int sum)
{
// Intially depth is 0 ans um is 0
depth++;
if (tree.left != null)
{
sum = depth + NodeDepth(tree.left, depth, sum);
}
if (tree.right != null)
{
sum = depth + NodeDepth(tree.right, depth, sum);
}
return sum;
}

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store