Reputation: 3177
Vertical Sum in a given Binary Tree
Given a Binary Tree, find vertical sum of the nodes that are in same vertical line. Print all sums through different vertical lines.
To understand what's same vertical line, we need to define horizontal distances first. If two nodes have the same Horizontal Distance (HD), then they are on same vertical line. The idea of HD is simple. HD for root is 0, a right edge (edge connecting to right subtree) is considered as +1 horizontal distance and a left edge is considered as -1 horizontal distance. For example, in the above tree, HD for Node 4 is at -2, HD for Node 2 is -1, HD for 5 and 6 is 0 and HD for node 7 is +2.
Examples:
1
/ \
2 3
/ \ / \
4 5 6 7
The tree has 5 vertical lines
Vertical-Line-1 has only one node 4 => vertical sum is 4
Vertical-Line-2: has only one node 2=> vertical sum is 2
Vertical-Line-3: has three nodes: 1,5,6 => vertical sum is 1+5+6 = 12
Vertical-Line-4: has only one node 3 => vertical sum is 3
Vertical-Line-5: has only one node 7 => vertical sum is 7
So expected output is 4, 2, 12, 3 and 7
My solution: I think out a o(nlong(n)) solution for this problem. The idea is:
(1) using preorder traversal to get the HD for every node, and store the HD and its associated node in an array.
(2) sort the array by HD
(3) traversal the sorted array to print result.
I'm sure this is not the best one for this problem. Can anyone help me give a better solution?
Upvotes: 5
Views: 7981
Answers (10)
Reputation: 3251
Sorry for the late solution. There are couple of ways to solve this. Itay Karo has already given a good solution using hashmap. You can also use doubly linked link list:
- Start with the root node and empty double list listNode
- Add the value of the rootNode to the current listNode
- Now whenever you go left, pass listNode.left and root.left and call step1 and 2 recursively.
- Similarly for right node, pass listNode.right and root.right Here is the code:
printVerticalSum(TreeNode root)
{
if(root==null)
return -1;
allocate node doubleLinkList //initialize,
printVerticalSumUtil(root, doubleLinkList);
//write the function to print double linked list
System.out.println(doubleLinkList.toString())
}
printVerticalSumUtil(TreeNode root, ListNode listNode) { if(root==NULL) return;
if(root.left!=NULL) if(listNode.prev!=NULL) listNode.prev.data += root.data; else ListNode t = new ListNode(root.data); t.next=listNode; listNode.prev = t; findVerticalSum(root.left, listNode.prev)
if(root.right!=NULL) if(listNode.next!=NULL) listNode.next.data += root.data; else ListNode t = new ListNode(root.data); t.prev=listNode; listNode.next = t; findVerticalSum(root.right, listNode.next) } More details here - https://k5kc.com/cs/algorithms/find-vertical-sum-in-binary-tree/. Thanks.
Upvotes: 0
Reputation: 61
Here is my solution in C#: please note the order matters how it outputs so I had to create a class and apply custom sort.
public class Location
{
public int x, y, val;
public Location(int x, int y, int val)
{
this.x = x;
this.y = y;
this.val = val;
}
}
private List<Location> locations;
public IList<IList<int>> VerticalTraversal(TreeNode root)
{
// Each location is a node's x position, y position, and value
locations = new List<Location>();
dfs(root, 0, 0);
locations.Sort(Comparer<Location>.Create((a,b) =>
{
if (a.x != b.x)
return a.x.CompareTo(b.x);
return a.y != b.y ? a.y.CompareTo(b.y) : a.val.CompareTo(b.val);
}));
var result = new List<IList<int>>();
result.Add(new List<int>());
int prev = locations[0].x;
foreach(Location loc in locations)
{
// If the x value changed, it's part of a new report.
if (loc.x != prev)
{
prev = loc.x;
result.Add(new List<int>());
}
// We always add the node's value to the latest report.
result[result.Count - 1].Add(loc.val);
}
return result;
}
private void dfs(TreeNode node, int x, int y)
{
if (node != null)
{
locations.Add(new Location(x, y, node.val));
dfs(node.left, x - 1, y + 1);
dfs(node.right, x + 1, y + 1);
}
}
Upvotes: 0
Reputation: 812
Here is My easy Solution in c++:- here i am using map to store the sum on basis of horizontal distance from center.
Node *vsumprint(Node *root,int level,map<int,int> &mp){
if(root==NULL)return NULL;
Node *temp = vsumprint(root->left,--level,mp);
if(temp==NULL){
level++;
}
if(mp.find(level)!=mp.end()){
mp[level] = root->data+mp[level];
}
else{
mp[level] = root->data+mp[level];
}
return vsumprint(root->right,++level,mp);
}
void printVertical(Node *root)
{
map<int,int> mp;
vsumprint(root,0,mp);
for(auto it:mp){
cout<<it.second<<" ";
}
}
Upvotes: 0
Reputation: 1389
//Tested and working example
package tree;
import java.util.TreeMap;
public class VerticalSumProblem
{
public static void main(String[] args)
{
VerticalSumProblem verticalSum = new VerticalSumProblem();
TreeNode treeNode = verticalSum.new TreeNode(1);
treeNode.left = verticalSum.new TreeNode(2);
treeNode.right = verticalSum.new TreeNode(3);
treeNode.left.left = verticalSum.new TreeNode(4);
treeNode.left.right = verticalSum.new TreeNode(5);
treeNode.right.left = verticalSum.new TreeNode(6);
treeNode.right.right = verticalSum.new TreeNode(7);
//treeNode.right.right.left =verticalSum.new TreeNode(8);
verticalSum.printTree(treeNode);
verticalSum.findVerticalSum(treeNode);
}
private void findVerticalSum(TreeNode root)
{
if(root == null) return;
TreeMap<Integer,Integer> _mappings = new TreeMap<Integer,Integer>();
findVerticalSum(root,_mappings,0);
if (_mappings != null)
{
System.out.println(_mappings.entrySet());
}
}
//if goes left -- and if goes right ++
private void findVerticalSum(TreeNode treeNode,TreeMap<Integer,Integer> mappings, int level)
{
if(treeNode == null) return;
TreeNode treeNodeLeft,treeNodeRight;
if(treeNode.left != null)
{
treeNodeLeft = treeNode.left;
findVerticalSum(treeNodeLeft, mappings,level - 1);
}
int sum = mappings.get(level) == null ? 0 : mappings.get(level);
mappings.put(level, treeNode.data + sum);
if( treeNode.right != null)
{
treeNodeRight = treeNode.right;
findVerticalSum(treeNodeRight,mappings, level + 1);
}
}
/* Create following Binary Tree
1
/ \
2 3
/ \ / \
4 5, 6 7
*/
private void printTree(TreeNode treeNode)
{
TreeNode treeNodeLeft,treeNodeRight;
if(treeNode == null) return;
if(treeNode.left != null || treeNode.right != null)
{
treeNodeLeft = treeNode.left;
treeNodeRight = treeNode.right;
System.out.println("rootValue ="+treeNode.data);
System.out.println("Left child of ="+treeNode.data +" is : "+ getNodedata(treeNodeLeft));
System.out.println("Right child of ="+treeNode.data+" is : "+ getNodedata(treeNodeRight)+"\n");
printTree(treeNodeLeft);
printTree(treeNodeRight);
}
}
private int getNodedata(TreeNode treeNode)
{
if(treeNode != null)
{
return treeNode.data;
}
return -1;
}
private class TreeNode
{
private int data;
private TreeNode left,right;
TreeNode(int data)
{
this.data = data;
left = null;
right = null;
}
}
}
//vertical sum
/// | | | | |
// | | 1 | |
/// | 2 | 3 |
// 4 | 5,6 | 7
// 0
// 1 -1
// 2 0,0 -2
//
Upvotes: 0
Reputation: 11
The following code will do the job :
Language Used : Java
// Algorithm for calculating the vertical sum of a binary tree.
static void verticalSum(Node root, int[] sum, int index)
{
/*
The sum array contains the sum of each
vertical line starting from the leftmost vertical line.
*/
if(root==null)
{
return;
}
else
{
sum[index]+=(int)root.data;
verticalSum(root.left, sum, index-1);
verticalSum(root.right, sum, index+1);
}
}
You need to invoke the above function using following code :
//Algorithm for calculating the vertical sum of a binary tree.
int level=countLevels(root);
int a=1,d=2,n=level;
int sizeOfArray= a+(n-1)*d;
int index=sizeOfArray/2;
int[] sum=new int[sizeOfArray];
verticalSum(root, sum, index);
System.out.print("Vertical Sum of the binary tree is : ");
for(int i=0;i<sizeOfArray;i++)
{
System.out.print(", " + sum[i]);
}
The countLevels(root) function is supplied below :
// Algorithm for calculating the number of levels
static int countLevels(Node root)
{
int count=0,c=1,i=0,level=0;
Queue<Node> queue=new LinkedList<Node>();
Node temp = null;
queue.add(root);
while(true)
{
if(queue.isEmpty())
{
break;
}
level++;
for(i=0;i<c;i++)
{
temp=queue.remove();
if(temp.left!=null)
{
queue.add(temp.left);
count++;
}
if(temp.right!=null)
{
queue.add(temp.right);
count++;
}
}
c=count;
count=0;
}
return level;
}
Upvotes: 0
Reputation: 11
#define HD_OFFSET 16
void vertical_sum(Node *node, int hd, int sum[], int *min, int *max){
/* We are offseting the index to access array correctly.
Root will be at HD_OFFSET/2 index and all vertical lines on left will
be at 0 to HD_OFFSET/2 and right side will be on HD_OFFSET/2 to HD_OFFSET */
int index = hd + HD_OFFSET/2;
if(!node) return;
/* to keep track of min and max index filled in sum array */
if(index > (*max)) (*max) = index;
if(index < (*min)) (*min) = index;
sum[index]+= node->value;
/*If we are moving on the left side,
we will pass index as one less the current */
vertical_sum(node->left, hd-1, sum, min, max);
/*If we are moving on the right side,
we will pass index as one more the current */
vertical_sum(node->right, hd+1, sum, min, max);
}
Upvotes: 0
Reputation: 115
This is my solution which runs in O(n)`
#include <iostream>
#include <vector>
using namespace std;
vector<int> v;
int size;
typedef struct node
{
int data;
struct node *left, *right ;
} node, *ptr;
ptr newNode(int item)
{
ptr temp = new node;
temp->data = item;
temp->left = temp->right = NULL;
return temp;
}
void printVerticalSumUtil(ptr root, int line)
{
if (root == NULL) return;
else
{
v[line] += root->data;
printVerticalSumUtil(root->left, line - 1);
printVerticalSumUtil(root->right, line + 1);
}
}
void printVerticalSum(ptr root)
{
if (root == NULL)
return;
//Calculating the line No for the root
ptr curr = root;
int line = 0;
while (curr->left != NULL)
{
curr = curr->left;
line++;
}
size = 2 * line + 1; //Total No of Lines
line++; //Adjusting line no for root
for (int i = 1; i <= size; ++i) //Initializing lines to zero
v.push_back(0);
printVerticalSumUtil(root, line);
for (int i = 1; i <= size; ++i)
{
cout << "Sum of Line " << i << " is " << v[i] << endl;
}
}
int main()
{
ptr root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->left = newNode(6);
root->right->right = newNode(7);
printVerticalSum(root);
return 0;
}`
Upvotes: 0
Reputation: 1
Using level order traversal, use a queue with elements and adjacently their HD values. The following algorithm will give solution in O(n) [not run-tested]
void findVertSum( struct node *root)
{
enqueue(root);
enqueue(0);
while(!isEmptyQueue())
{
tempnode = dequeue();
vertIndex = dequeue();
sum[vertIndex] += tempnode->val;
// Array cant be used because there will be sum[-1], sum[-2] etc, which will give error. This line hense only gives the idea to store solution.
if(t->left)
{
enqueue(t->left);
enqueue(vertIndex - 1);
}
if(t->right)
{
enqueue(t->right);
enqueue(vertIndex + 1);
}
}
Upvotes: 0
Reputation: 23
here's one in C. the vsum array upon return will have the results.
void vsum(struct tree *t, int vsum[], int depth) {
if (t == NULL)
return;
vsum[depth] += t->val;
depth++;
vsum(t->left, vsum, depth);
vsum(t->right, vsum, depth);
}
Upvotes: 0
Reputation: 18286
Can't you do it all in the first traversal? Define a dictionary (hash map) from HD to sum.
And for each node you visit add its value to the right dictionary key - this is a O(n) solution.
d = {}
def traverse(node, hd):
if not node:
return
if not hd in d:
d[hd] = 0
d[hd] = d[hd] + node.value
traverse(node.left, hd - 1)
traverse(node.right, hd + 1)
Then just call traverse(root, 0)
Upvotes: 12
Related Questions
- Binary Tree branch sums without recursion
- Sum of Each Branch in a Binary Search Tree
- Sum of all leaf nodes at minimum level in binary tree
- Binary Tree Path Sum logic
- Each subtree sum in a binary tree in O(N) time and O(1) space?
- Summing elements of binary tree in Java
- Tree - path sum
- Calculating the vertical sum in binary tree
- Balanced sums in binary tree
- Binary tree where value of each node holds the sum of child nodes