Sunday, March 18, 2012

Leaf nodes in Binary Tree.


Given a binary tree, find 2 leaf nodes say X and Y such that F(X,Y) is maximum where F(X,Y) = sum of nodes in the path from root to X + sum of nodes in the path from root to Y - sum of nodes in the common path from root to first common ancestor of the Nodes X and Y




Approach:
1. Store all the paths from root to leafs.
2. for each path i,j from root to leaf calculate 
a = sum of nodes in the path from root to X
b = sum of nodes in the path from root to Y
c = sum of nodes in the common path from root to first common ancestor of the Nodes X and Y
Let max fxy be the maximum for F(X,Y).
if ((a+b-c) > fxy) { fxy <= (a+b-c) } and also store the leaf(i) and leaf(j).


Code input/output:

printing inorder: 
1 3 4 6 7 8 10 13 14 
printing the path map: 
{0=[8, 3, 1], 1=[8, 3, 6, 4], 2=[8, 3, 6, 7], 3=[8, 10, 14, 13]}
12:21:11
1 : 4
12:24:11
1 : 7
12:45:8
1 : 13
21:24:17
4 : 7
21:45:8
4 : 13
24:45:8
7 : 13
Max F(X,Y): 61
Leaf1: 7
Leaf2: 13


No comments:

Post a Comment