Binary search tree in Python
Binary Search Tree is a binary tree data structure which has the following properties:
- The left subtree of a node contains only nodes with values smaller than the node.
- The right subtree of a node contains only nodes with values greater than the node.
- The left and right subtree each must also be a binary search tree.
Based on the properties, we can implement a algorithm to check if a binary tree is binary search tree.
import sys
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
# left most node is minimum
def minVal(node):
current = node
while current.left != None:
current = current.left
return current.val
# right most node is maximum
def maxVal(node):
current = node
while current.right != None:
current = current.right
return current.val
# not efficient since some nodes are traversed multiple times
def isBst(node):
if node == None:
return True
if node.left and node.val < minVal(node.left):
return False
if node.right and node.val > maxVal(node.right):
return False
if (not isBst(node.left)) or (not isBst(node.right)):
return False
return True
def isBstOptimal(node, min, max):
if node == None:
return True
if node.val < min or node.val > max:
return False
return isBstOptimal(node.left, min, node.val) and isBstOptimal(
node.right, node.val, max
)
def binarySearch(node, target):
if node == None:
return False
if node.val == target:
return True
if node.val > target:
return binarySearch(node.left, target)
elif node.val < target:
return binarySearch(node.right, target)
#
# 6
# / \
# 4 8
# / \ / \
# 2 5 7 9
# / \
# 1 3
#
root = Node(6)
n1 = Node(4)
n2 = Node(8)
root.left = n1
root.right = n2
n3 = Node(2)
n4 = Node(5)
n1.left = n3
n1.right = n4
n5 = Node(7)
n6 = Node(9)
n2.left = n5
n2.right = n6
n7 = Node(1)
n8 = Node(3)
n3.left = n7
n3.right = n8
print(isBst(root))
print(isBstOptimal(root, -sys.maxsize, sys.maxsize))
n9 = Node(9)
n7.left = n9
print(isBst(root))
print(isBstOptimal(root, -sys.maxsize, sys.maxsize))
print(binarySearch(root, 8))
print(binarySearch(root, 11))
print(binarySearch(root, -1))