Grokking - Tree Module
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253
from binaryTreeNode import *
from ppbtree import *
class InorderIterator:
def __init__(self, root):
self.stk = []
# Assuming that when iterator is initialized
# it is always at the first element of tree in its in-order
self.populate_iterator(root)
def populate_iterator(self, root):
while root != None:
self.stk.append(root)
root = root.left
def hasNext(self):
if not self.stk:
return False
else:
return True
# getNext returns null if there are no more elements in tree
def getNext(self):
if not self.stk:
return None
r_val = self.stk[-1]
del self.stk[-1]
# self.stk.remove(-1)
temp = r_val.right;
self.populate_iterator(temp)
return r_val
# if you need to provide current element, that will be at top of stack always
def inorder_using_iterator(root):
iter = InorderIterator(root)
mystr = ""
while iter.hasNext():
ptr = iter.getNext()
mystr += str(ptr.data) + " "
return mystr
arr = [25,125,200,300,75,50,12,35,60,75]
root = create_BST(arr)
display_level_order(root)
print()
print_tree(root)
print("is BST? " + str(is_BST(root, float('-inf'), float('inf'))))
print("Inorder Iterator = ", end = "")
print(inorder_using_iterator(root))
Python
INFO