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

Question — 8(Level — Easy)

Welcome to the competitive series of Code Wrestling. Today, we are gonna solve an easy problem, Node Depth in Binary Tree.

We will find the Time and Space complexity of our solution and will also guide you to the process of finding an optimized solution.

Visit our YouTube channel for more interesting stuff Code Wrestling.

Code Wrestling

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.

STOP HERE. And read the question again. Try to solve the question on your own and then proceed further to see our solution.

Solution

The problem can be easily solved by using Recursion.

The above picture gives a little insight into how you can approach your solution.

At any level/depth, add the currentDepth + getAllLeftNodeDepth() + getAllRightNodeDepth()

See the below code snippet to understand the 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);
}

The time complexity for the solution is O(n) because we have to traverse each element in the tree and the space complexity is also O(h) where h is the height of the binary tree in this case (it depends on how the tree looks like), because of the recursion.

In case if you don’t understand the solution well, I have a more descriptive solution just to make you understand the solution.

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;
}

Thank you so much for reading till the end. See you in the next article. Till then… HAPPY LEARNING!!

Do visit our YouTube channel Code Wrestling for more interesting stuff.