Binary Search Tree
Binary Search Tree is a node-based binary tree data structure that has the following properties:
- The left subtree of a node contains only nodes with keys lesser than the node’s key.
- The right subtree of a node contains only nodes with keys greater than the node’s key.
- The left and right subtree each must also be a binary search tree.
The above properties of the Binary Search Tree provide an ordering among keys so that the operations like search, minimum and maximum can be done fast. If there is no order, then we may have to compare every key to search for a given key.
Searching Element
- Start from the root.
- Compare the searching element with root, if less than root, then recurse for left, else recurse for right.
- If the element to search is found anywhere, return true, else return false.
# A utility function to search a given key in BST
def search(root,key):
# Base Cases: root is null or key is present at root
if root is None or root.val == key:
return root
# Key is greater than root's key
if root.val < key:
return search(root.right,key)
# Key is smaller than root's key
return search(root.left,key)
Insertion of a key
- Start from the root.
- Compare the inserting element with root, if less than root, then recurse for left, else recurse for right.
- After reaching the end, just insert that node at left(if less than current) else right.
# Python program to demonstrate
# insert operation in binary search tree
# A utility class that represents
# an individual node in a BST
class Node:
def __init__(self, key):
self.left = None
self.right = None
self.val = key
# A utility function to insert
# a new node with the given key
def insert(root, key):
if root is None:
return Node(key)
else:
if root.val == key:
return root
elif root.val < key:
root.right = insert(root.right, key)
else:
root.left = insert(root.left, key)
return root
# A utility function to do inorder tree traversal
def inorder(root):
if root:
inorder(root.left)
print(root.val)
inorder(root.right)
# Driver program to test the above functions
# Let us create the following BST
# 50
# / \
# 30 70
# / \ / \
# 20 40 60 80
r = Node(50)
r = insert(r, 30)
r = insert(r, 20)
r = insert(r, 40)
r = insert(r, 70)
r = insert(r, 60)
r = insert(r, 80)
# Print inorder traversal of the BST
inorder(r)
Output
20 30 40 50 60 70 80
More Articles on Binary Search Tree
Learn DSA with Python | Python Data Structures and Algorithms
This tutorial is a beginner-friendly guide for learning data structures and algorithms using Python. In this article, we will discuss the in-built data structures such as lists, tuples, dictionaries, etc, and some user-defined data structures such as linked lists, trees, graphs, etc, and traversal as well as searching and sorting algorithms with the help of good and well-explained examples and practice questions.