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))
from collections import deque
# =================================
# insert
# find_in_bst
# find_node
# display_inorder
# create_BST
# create_binary_tree
# create_random_BST
# bst_to_list_rec
# bst_to_list
# insert_at_head
# populate_parents_rec
# populate_parents
# display_level_order
# get_level_order
# get_inorder_helper
# get_inorder
# is_identical_tree
# =================================
class BinaryTreeNode:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
# below data members used only for some of the problems
self.next = None
self.parent = None
self.count = None
def insert(root, d):
pNew = BinaryTreeNode(d)
if root == None:
return pNew
parent = None
pTemp = root
while (pTemp != None):
parent = pTemp
if d < pTemp.data:
pTemp = pTemp.left
else:
pTemp = pTemp.right
if d < parent.data:
parent.left = pNew
else:
parent.right = pNew
return root
def find_in_bst(root, d):
if root == None:
return None
if root.data == d:
return root
elif root.data > d:
return find_in_bst(root.left, d)
else:
return find_in_bst(root.right, d)
# find node in inorder
# works for both BST and binary tree
def find_node(root, d):
if root == None:
return
if root.data == d:
return root
temp = find_node(root.left, d)
if temp != None:
return temp
return find_node(root.right, d)
def display_inorder(node):
if node == None:
return
display_inorder(node.left)
print(str(node.data), end = ", ")
display_inorder(node.right)
def create_BST(arr):
root = None
for x in arr:
root = insert(root, x)
return root
def create_binary_tree(count):
root = None
for i in range(1, count):
root = insert(root, random.randrange(1,100))
return root
def create_random_BST(count):
root = None;
for i in range(1, count):
root = insert(root, random.randrange(200, 300))
return root
def bst_to_list_rec(root, lst):
if root == None:
return
bst_to_list_rec(root.left, lst)
lst.append(root.data)
bst_to_list_rec(root.right, lst)
def bst_to_list(root):
lst = []
bst_to_list_rec(root, lst)
return lst
def insert_at_head(head, data):
newNode = LinkedListNode(data)
newNode.next = head
return newNode
def populate_parents_rec(root, parent):
if root == None:
return
root.parent = parent
populate_parents_rec(root.left, root)
populate_parents_rec(root.right, root)
def populate_parents(root):
populate_parents_rec(root, None)
def display_level_order(root):
if root == None:
return
q = deque()
q.append(root)
while q:
temp = q.popleft()
print(str(temp.data), end = ",")
if temp.left != None:
q.append(temp.left)
if temp.right != None:
q.append(temp.right)
# print()
def get_level_order(root):
output = []
if root == None:
return output
q = deque()
q.append(root)
while q:
temp = q.popleft()
output.append(temp.data)
if temp.left != None:
q.append(temp.left)
if temp.right != None:
q.append(temp.right)
return output
def get_inorder_helper(root, output):
if root == None:
return output
output = get_inorder_helper(root.left, output)
output.append(root.data)
output = get_inorder_helper(root.right, output)
return output
def get_inorder(root):
output = []
return get_inorder_helper(root, output)
def is_identical_tree(root1,root2):
if root1 == None and root2 == None:
return True
if root1 != None and root2 != None and root1.data == root2.data:
return is_identical_tree(root1.left,root2.left) and is_identical_tree(root1.right,root2.right)
return False
def is_BST(root, min_value=float('-inf'), max_value=float('inf')):
if not root:
return True
if root.data < min_value or root.data > max_value:
return False
return is_BST(root.left, min_value, root.data) and is_BST(root.right, root.data, max_value)
# -*- coding: utf-8 -*-
"""
based on Clement Michard (c) 2015
Vladyslav Khardel (c) 2017
"""
# =================================
# print_tree
# =================================
def print_tree(current_node, nameattr='data', left_child='right', right_child='left', indent='', last='updown'):
if hasattr(current_node, nameattr):
name = lambda node: getattr(node, nameattr)
else:
name = lambda node: str(node)
up = getattr(current_node, left_child)
down = getattr(current_node, right_child)
if up is not None:
next_last = 'up'
next_indent = '{0}{1}{2}'.format(indent, ' ' if 'up' in last else '|', ' ' * len(str(name(current_node))))
print_tree(up, nameattr, left_child, right_child, next_indent, next_last)
if last == 'up': start_shape = '┌'
elif last == 'down': start_shape = '└'
elif last == 'updown': start_shape = ' '
else: start_shape = '├'
if up is not None and down is not None: end_shape = '┤'
elif up: end_shape = '┘'
elif down: end_shape = '┐'
else: end_shape = ''
print('{0}{1}{2}{3}'.format(indent, start_shape, name(current_node), end_shape))
if down is not None:
next_last = 'down'
next_indent = '{0}{1}{2}'.format(indent, ' ' if 'down' in last else '|', ' ' * len(str(name(current_node))))
print_tree(down, nameattr, left_child, right_child, next_indent, next_last)
