Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Approach1
2.1.
Algorithm
2.2.
Implementation
2.2.1.
Complexity Analysis
3.
Approach 2
3.1.
Algorithm
3.2.
Implementation
3.2.1.
Complexity Analysis
4.
Frequently Asked Questions
4.1.
What is the use of a binary tree?
4.2.
What is a node in a binary tree?
4.3.
How can we calculate the diagonal sum of a binary tree?
5.
Conclusion
Last Updated: Mar 27, 2024
Easy

Diagonal Sum of a Binary Tree

Author Palak Mishra
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

In this blog, we are provided with a  binary tree problem. The task is to find the sum of all the diagonal elements of the respective binary tree. Before moving further, please take note that all of the right branches are drawn parallel to one another, and the same is true for all of the left branches.

Now, let's understand what we have to implement in the problem statement:

Problem Statement

Determine the sum of all nodes for each diagonal with a negative slope given a binary tree. Assume that a node's left and right children are at a 45-degree angle with the parent.

Sample Examples

Example 1:

Here for the input tree,

 

Output: 

18 11 26

 

Explanation:

As we see in the diagram,
Sum of 4, 6 and 8 = 18 
Sum of 2, 3, 1,and 5= 11 
Sum of 7, 10 and 9 = 26


Example 2:

Here for the input tree,

 

Output: 

18 39 29

Explanation:

As we see in the diagram,

Sum of 2, 5 and 11 = 18 
Sum of 3, 9,10, and 17= 39 
Sum of 6, 10 and 13= 29

Approach1

With the aid of hashing, we can quickly resolve this problem. The goal is to construct an empty map, where each key corresponds to a binary tree diagonal and each value maintains the total number of nodes that make up the diagonal. Then update the map after preorder traversal of the tree. Increase the diagonal by one for each node's left subtree and repeat with the same diagonal for each node's right subtree.

Algorithm

  1. Establish a data structure to hold a binary tree node.
     
  2. Construct a recursive function to preorder traverse the tree and fill the map with the diagonal sum of the elements.
     
  3. Update the current diagonal with the value of the node
     
  4. Repeat with the diagonal raised by 1 for the left subtree.
     
  5. Repeat for the right subtree along the identical diagonal
     
  6. Create a function that prints the diagonal sum of a binary tree
     
  7. Make an empty map and enter the diagonal sum for each slope in it.
     
  8. Fill the map by traversing the tree in a preorder fashion 
     
  9. Traverse the map and print the diagonal sum.

 

Implementation

#include <iostream>
#include <unordered_map>
using namespace std;
 
struct Node
{
    int data;
    Node *left, *right;
    Node(int data)
    {
        this->data = data;
        this->left = this->right = nullptr;
    }
};
 
void diagonalSum(Node* root, int diagonal, auto &map)
{  if (root == nullptr) {
        return;
    }  
    map[diagonal] += root->data;
    diagonalSum(root->left, diagonal + 1, map);
    diagonalSum(root->right, diagonal, map);
} 
void diagonalSum(Node* root)
{ 
    unordered_map<int, int> map;
    diagonalSum(root, 0, map);
    for (int i = 0; i < map.size(); i++) {
        cout << map[i] << " ";
    }
}
 int main()
{
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->right->left = new Node(5);
    root->right->right = new Node(6);
    root->right->left->left = new Node(7);
    root->right->left->right = new Node(8);
    diagonalSum(root);
    return 0;
}

 

Output: 

10 15 11

 

Complexity Analysis

Time Complexity:  O(n), As the given program requires preorder traversal of the binary tree. So, the time complexity is O(n). As the input grows, the algorithm takes proportionally longer to complete. 

Space Complexity: O(n) As the given program contains a map, linear space complexity occurs.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Approach 2

This is another approach to calculating the diagonal sum of a binary tree. There is no requirement to use a map with more space. Queue used for left node left element for future processing.

Algorithm

  1. Form a Node Structure, For level-index mapping for the node
     
  2. To create new nodes, write a function.
     
  3. To store the diagonal sum, create a list.
     
  4. To process diagonal left while traversing right, create a list.
     
  5. Create a queue.
     
  6. Take the sum variable to add the diagonal elements together.
     
  7. Do the next diagonal's element count by using the count variable.
     
  8. Determine how many elements are necessary to complete the current diagonal by using a diagonal variable.
     
  9. Use a loop to find the count of the following diagonal elements, and move diagonally right.
     
  10. If root ==Null, every diagonal element has been traversed.
     
  11. If the traversal of all elements in the current diagonal has been completed(last ==0), check the queue for processing any remaining new diagonal sums.
     
  12. Keep the element on a diagonal by using last= count.
     
  13. Assemble a binary tree in the driver code
     
  14. Call the Function
     
  15. Print the diagonal sums 

Implementation

#include<bits/stdc++.h>
using namespace std;

struct Node
{
  int data;
  Node *left,*right;
};

Node* newNodeofBT(int data)
{
  Node* node = new Node();
  node->data = data;
  node->left = node->right = NULL;
  return node;
}

vector<int> diagonalSumofBT(Node* root){

vector<int>list;

queue<Node*>Queue;
int sum = 0;
int count = 0;
int last = 0;

while(root != NULL)
{
  if(root->left != NULL)
   { 
     Queue.push(root->left);
     count++; 
   }
  sum += root->data;
  root = root->right;
  
  if(root == NULL){
     if(!Queue.empty()){ 
        root = Queue.front();
        Queue.pop();
     }
     
     
      if(last == 0){
      list.push_back(sum);
      sum = 0;
      last = count;
      count = 0;
     }
   last--;
  }
 }
 return list;

}

int main()
{

  Node* root = newNodeofBT(1);
  root->left = newNodeofBT(2);
  root->right = newNodeofBT(3);
  root->left->left = newNodeofBT(9);
  root->left->right = newNodeofBT(6);
  root->right->left = newNodeofBT(4);
  root->right->right = newNodeofBT(5);
  root->right->left->right = newNodeofBT(7);
  root->right->left->left = newNodeofBT(12);
  root->left->right->left = newNodeofBT(11);
  root->left->left->right = newNodeofBT(10);

  vector<int>v = diagonalSumofBT(root);

  for (int i = 0; i < v.size(); i++)
  cout << v[i] << " ";
}

 

Output: 

9 19 42

 

Complexity Analysis

Time Complexity: O(n), Since we are using a loop to traverse the tree. So, as the input grows, the algorithm takes proportionally longer to complete. 

Space Complexity: O(n) As the above program contains a queue to store the elements for later processing, O(n) auxiliary space is required. Hene, linear space complexity occurs.

Frequently Asked Questions

What is the use of a binary tree?

Due to their ability to store data hierarchically, binary trees are mostly used in computers for searching and sorting. Insertion, deletion, and traversal are some typical operations that can be performed on binary trees.

What is a node in a binary tree?

A binary tree is built up of nodes, each composed of a data element, a "left" reference, and a "right" connection. The root is the topmost node of the tree.

How can we calculate the diagonal sum of a binary tree?

Construct an empty map, where each key corresponds to a binary tree diagonal, and each value maintains the total number of nodes that make up the diagonal. Then update the map after preorder traversal of the tree. Increase the diagonal by one for each node's left subtree and repeat with the same diagonal for each node's right subtree.

Conclusion

As discussed in this article, the problem "Diagonal Sum of a Binary Tree" asks you to return the sum of all the nodes that are part of the respective diagonal of the given binary tree. We use the Hashing and Queue Data Structure to get the desired result.

We hope that this article has helped you enhance your knowledge regarding the subject of the Diagonal sum of a Binary Tree.

After reading about the Binary tree, are you not feeling excited to read/explore more articles on this topic? Don't worry; Coding Ninjas has you covered. You can learn more about  Maximum Width In Binary Tree and Special Binary Tree. Also, see Binary Tree Zigzag Traversal and Number of balanced binary trees.

You can also practice some relevant problems at the code studio, such as:

  1. Preorder Binary Tree
  2. Construct Binary Tree From Inorder and Preorder Traversal
  3. Top View Of Binary Tree
  4. Height of the Binary Tree From Inorder and Level Order Traversal
  5. Boundary Traversal Of Binary Tree


Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But suppose you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Previous article
Construct an Ancestor Matrix from the given Binary Tree
Next article
Sum of heights of all individual nodes in a binary tree
Live masterclass