class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
class BinarySearchTree:
def __init__(self):
self.root = None
def insert(self, value):
node = Node(value)
# Check if root node exists
if self.root == None:
self.root = node
return self.root
# Use two pointers
currentNode = self.root
prevNode = None
# Iterate through the tree
# until a leaf node is reached
while currentNode:
prevNode = currentNode
if value < currentNode.value:
currentNode = currentNode.left
else:
currentNode = currentNode.right
# Attach the new node
# to the leaf node
if value < prevNode.value:
prevNode.left = node
else:
prevNode.right = node
return prevNode
def lookup(self, value):
# Use two pointers
currentNode = self.root
prevNode = None
# Iterate through the tree
# until a leaf node is reached
while currentNode:
prevNode = currentNode
if value < currentNode.value:
currentNode = currentNode.left
elif value > currentNode.value:
currentNode = currentNode.right
else:
return True
return False
def remove(self, value):
# Case 1: Node to remove is a leaf node
# Use two pointers
currentNode = self.root
prevNode = None
# Iterate through the tree
# until a leaf node is reached
while currentNode:
prevNode = currentNode
if value < currentNode.value:
currentNode = currentNode.left
elif value > currentNode.value:
currentNode = currentNode.right
else:
# Inorder Traversal (We get sorted
# order of elements in tree)
def print_tree(self):
if self.root != None:
self.printt(self.root)
def printt(self, curr_node):
if curr_node != None:
self.printt(curr_node.left)
print(str(curr_node.value))
self.printt(curr_node.right)
# Function to print level order traversal of tree
def printlevelorder(root):
h = height(root)
for i in range(1, h + 1):
printGivenLevel(root, i)
print()
def printGivenLevel(root, level):
if root is None:
return root
if level == 1:
print(root.value, end=' ')
elif level > 1:
printGivenLevel(root.left, level - 1)
printGivenLevel(root.right, level - 1)
""" Compute the height of a tree--the number of nodes
along the longest path from the root node down to
the farthest leaf node
"""
def height(node):
if node is None:
return 0
else:
# Compute the height of each subtree
lheight = height(node.left)
rheight = height(node.right)
# Use the larger one
if lheight > rheight:
return lheight+1
else:
return rheight+1
'''def traverse(node):
tree = {value: node.value}
tree.left = None if node.left == None else traverse(node.left)
tree.right = None if node.right == None else traverse(node.right)
return tree'''
tree = BinarySearchTree()
tree.insert(9)
tree.insert(4)
tree.insert(6)
tree.insert(20)
tree.insert(170)
tree.insert(15)
tree.insert(1)
tree.print_tree()
print("Level order traversal of binary tree is -")
printlevelorder(tree.root)
#JSON.stringify(traverse(tree.root))
#json.dumps(arr, separators=(',', ':'))
#json.dumps(traverse(tree.root))
# 9
# 4 20
# 1 6 15 170
