class BinarySearchTree:

def __init__(self, e = None):

self.left = self.right = None

self.data = e

def insert(self, e):

if self.data is None:

self.data = e

else:

if self.data >= e:

if self.left is None:

self.left = BinarySearchTree(e)

else:

self.left.insert(e)

else:

if self.right is None:

self.right = BinarySearchTree(e)

else:

self.right.insert(e)

def nextMin(self):

if self.left:

for x in self.left.nextMin():

yield x

yield self.data

if self.right:

for x in self.right.nextMin():

yield x

def nextMax(self):

if self.right:

for x in self.right.nextMax():

yield x

yield self.data

if self.left:

for x in self.left.nextMax():

yield x

def findxy(self, k):

if self.data:

mn = self.nextMin()

mx = self.nextMax()

m = mn.next()

n = mx.next()

while True:

sm = m + n

try:

if sm == k:

return m,n

elif sm < k :

m = mn.next()

else:

n = mx.next()

except:

return None

def main():

l = [50, 80, 30, 20, 40, 70, 60]

t = BinarySearchTree()

for i in l:

t.insert(i)

print t.findxy(120)

if __name__ == '__main__':

main()

### Like this:

Like Loading...

*Related*