Given a binary tree, Find the Maximum Path Sum between Any Two Leaves

from collections import deque
class node:
def __init__(self,data):
self.data=data
self.left=None
self.right=None
class tree:
def __init__(self,n):
self.root=n
self.maxPath=0
self.res1=[]
def insert(self,n1):
n=self.root
parent=None
while n:
parent=n
if n.data==n1.data:
return
elif n.data>n1.data:
n=n.left
else:
n=n.right
if parent:
if parent.data>n1.data:
parent.left=n1
else:
parent.right=n1
def levelOrder(self):
n=self.root
q=deque()
if n:
q.append(n)
print “LevelOrder : “,
while 1:
count=len(q)
if count==0:
break
while count>0:
e=q.popleft()
print e.data,
if e.left:
q.append(e.left)
if e.right:
q.append(e.right)
count-=1
print ”
def anyTwoLeavesMaxSum(self,n):
if n:
left=self.anyTwoLeavesMaxSum(n.left)
right=self.anyTwoLeavesMaxSum(n.right)
currSum=max(left+n.data,n.data+right,left+n.data+right)
if self.checkLeafNode(n.left)==False:
currSum=max(left,currSum)
if self.checkLeafNode(n.right):
currSum=max(right,currSum)
self.res2.append(currSum)
return max(left,right)+n.data
return 0
def checkLeafNode(self,n):
if n and n.left==None and n.right==None:
return True
return False
import math
l=5
n=int(math.pow(2,l))
Nodes=[node(i) for i in range(n)]
t=tree(Nodes[1])
for i in range(1,n/2):
Nodes[i].left=Nodes[2*i]
Nodes[i].right=Nodes[2*i+1]
#Nodes[1].left=None
Nodes[2].right=None
Nodes[4].left=None
Nodes[12].left=None;Nodes[12].right=None
Nodes[13].left=None;Nodes[13].right=None
Nodes[7].left=None
Nodes[15].left=None;Nodes[15].right=None;

t.levelOrder();
t.anyTwoLeavesMaxSum(t.root)
print t.res2 #_____the list of possible sums
print max(t.res2) #_______gives the maxSum