find two elements in a binary search tree whose sum is given k

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()
Advertisements

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