using iterators:
__author__ = 'deepika'
"""
This code will return iterator for inorder traversal of a BST
"""
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def __repr__(self):
return str(self.val)
class InorderIterator:
def __init__(self, root):
self.root = root
self.stack = []
self.appendLeftTree()
def appendLeftTree(self, start=None):
temp = self.root if start is None else start
while temp:
self.stack.append(temp)
temp = temp.left
def next(self):
if self.stack:
next_item = self.stack.pop()
if next_item.right:
self.appendLeftTree(next_item.right)
return next_item.val
return None
class ReverseInOrderIterator:
def __init__(self, root):
self.root = root
self.stack = []
self.appendRightTree()
def appendRightTree(self, start=None):
temp = self.root if start is None else start
while temp:
self.stack.append(temp)
temp = temp.right
def next(self):
if self.stack:
next_item = self.stack.pop()
if next_item.left:
self.appendRightTree(next_item.left)
return next_item.val
return None
class Solution:
def binarySearchBST(self, root, key):
left_itr = InorderIterator(root)
right_itr = ReverseInOrderIterator(root)
left_val = left_itr.next()
right_val = right_itr.next()
while True:
if left_val >= right_val:
break
if left_val + right_val == key:
print " Found: ", left_val, " ", right_val
if left_val + right_val < key:
left_val = left_itr.next()
else:
right_val = right_itr.next()
root=TreeNode(10)
root.left=TreeNode(5)
root.right=TreeNode(11)
root.left.left=TreeNode(1)
root.left.right=TreeNode(8)
root.left.right.left=TreeNode(7)
root.right.right=TreeNode(14)
itr = InorderIterator(root)
result = []
for i in range(7):
result.append(itr.next())
print result
result = []
itr = ReverseInOrderIterator(root)
for i in range(7):
result.append(itr.next())
print result
s=Solution()
s.binarySearchBST(root, 18)
On Sunday, September 2, 2012 at 1:02:57 PM UTC-7, Navin Kumar wrote:
>
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
