Binary tree traversal

Question

find the vertical sum of a binary tree. For example,the tree has 5 vertical lines?

Comments

It is any rule that $1,5,6$ take one vertical line?

---

Yes..check the link..it's written there.. The nodes which have same horizontal distances(HD) then they are on the same vertical line. HD is calculated from root.

Distance from root to root is 0. So HD(1)=0

If we go to left side we consider it to be negative distance while going towards right mark the edge as +ve.

So we start marking :

E(1,2)= -1

E(2,4)=-1

E(2,5)=1

E(1,3)=1

E(3,6)=-1

E(3,7)=1

Now to get HD we do like:

HD(2)= E(1,2)=-1

HD(4)=E(1,2)+E(2,4) = -1+ -1 =-2

HD(5)=E(1,2)+E(2,5)=-1+1=0

HD(3)=E(1,3)=1

HD(6)=E(1,3)+E(3,6)=+1-1=0

HD(7)=E(1,3)+E(3,7)=1+1=2

Since HD of 1,5,6 are 0 so they are in the same vertical line.

---

thanks