Vertical sums of a binary tree

The problem is to print the vertical sums of a binary tree 
for example
|      |       5        |     |
| | / | \ | |
| | / | 8 |
| | / | / | \|
| 4 | / | 10
| / | \ 9 | |
| / | \ | |
7 | 6 |
| | | | |
| | | | |
-----------------------------
7 4 20 8 10


from collections import defaultdict
from operator import itemgetter

verticalSum = defaultdict(int)

def findVerticalSum(t, v):

if t:
verticalSum[v] += t["d"]
findVerticalSum(t["left"], v - 1)
findVerticalSum(t["right"], v + 1)



t = {
"d" : 5,
"left" : {

"d" : 4,
"left" : {
"d" : 7,
"left" : None,
"right" : None

},
"right" : {
"d" : 6,
"left" : None,
"right" : None
}
},
"right" : {
"d" : 8,
"left" : {
"d": 9,
"left" : None,
"right" : None
},

"right" : {
"d" : 10,
"left" : None,
"right" : None
}

}
}

findVerticalSum(t, 0)

print [a[1] for a in sorted(verticalSum.items(), key=itemgetter(0))]
Advertisements

2 thoughts on “Vertical sums of a binary tree

  1. static int arr1[]=new int[6]; static void verticalprint(Node root,int pos) { if(root==null) return; arr1[pos]+=root.data; verticalprint(root.left, pos-1); verticalprint(root.right, pos+1); }//calling functionverticalprint(root,2);

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s