All Courses
AI Career Planner
1:1 Coaching/Mentoring
Job Board
SQL
HTML/CSS/JS
Coding
Settings
LogoutHello Everyone,
Given a Binary Tree, find vertical sum of the nodes that are in same vertical line. Print all sums through different vertical lines.
Below is algorithm.
verticalSumDLL(root)
1) Create a node of doubly linked list node with value 0. Let the node be llnode.
2) verticalSumDLL(root, llnode)
verticalSumDLL(tnode, llnode)
1) Add current node’s data to its vertical line
llnode.data = llnode.data + tnode.data;
2) Recursively process left subtree
// If left child is not empty if (tnode.left != null) {
if (llnode.prev == null) { llnode.prev = new LLNode(0); llnode.prev.next = llnode; }
verticalSumDLLUtil(tnode.left, llnode.prev) ;
}
3) Recursively process right subtree
if (tnode.right != null) { if (llnode.next == null) {
llnode.next = new LLNode(0);
llnode.next.prev = llnode;
}
verticalSumDLLUtil(tnode.right, llnode.next) ;
}
Code:
/// C++ program of space optimized solution
/// to find vertical sum of binary tree.
#include <bits/stdc++.h>
using namespace std;
/// Tree node structure
struct TNode{
int key;
struct TNode *left, *right;
};
/// Function to create new tree node
TNode* newTNode( int key)
{
TNode* temp = new TNode;
temp->key = key;
temp->left = temp->right = NULL;
return temp;
}
/// Doubly linked list structure
struct LLNode{
int key;
struct LLNode *prev, *next;
};
/// Function to create new Linked List Node
LLNode* newLLNode( int key)
{
LLNode* temp = new LLNode;
temp->key = key;
temp->prev = temp->next = NULL;
return temp;
}
/// Function that creates Linked list and store
/// vertical sum in it.
void verticalSumDLLUtil(TNode *root, LLNode *sumNode)
{
/// Update sum of current line by adding value
/// of current tree node.
sumNode->key = sumNode->key + root->key;
/// Recursive call to left subtree.
if (root->left)
{
if (sumNode->prev == NULL)
{
sumNode->prev = newLLNode(0);
sumNode->prev->next = sumNode;
}
verticalSumDLLUtil(root->left, sumNode->prev);
}
/// Recursive call to right subtree.
if (root->right)
{
if (sumNode->next == NULL)
{
sumNode->next = newLLNode(0);
sumNode->next->prev = sumNode;
}
verticalSumDLLUtil(root->right, sumNode->next);
}
}
/// Function to print vertical sum of Tree.
/// It uses verticalSumDLLUtil() to calculate sum.
void verticalSumDLL(TNode* root)
{
/// Create Linked list node for
/// line passing through root.
LLNode* sumNode = newLLNode(0);
/// Compute vertical sum of different lines.
verticalSumDLLUtil(root, sumNode);
/// Make doubly linked list pointer point
/// to first node in list.
while (sumNode->prev != NULL){
sumNode = sumNode->prev;
}
/// Print vertical sum of different lines
/// of binary tree.
while (sumNode != NULL){
cout << sumNode->key << " " ;
sumNode = sumNode->next;
}
}
int main()
{
/*
1
/ \
/ \
2 3
/ \ / \
/ \ / \
4 5 6 7
*/
TNode *root = newTNode(1);
root->left = newTNode(2);
root->right = newTNode(3);
root->left->left = newTNode(4);
root->left->right = newTNode(5);
root->right->left = newTNode(6);
root->right->right = newTNode(7);
cout << "Vertical Sums are\n" ;
verticalSumDLL(root);
return 0;
}
Output :
Vertical Sums are 4 2 12 3 7