Binary Search Tree
Data Structures and Algorithms Note
Published in
3 min readJan 31, 2022
What is Binary Search Tree
- nodes on the left subtree are all smaller than the node’s data
- nodes on the right subtree are all bigger than the node’s data
- the left and right subtree are also binary search tree
Search a node
Similar to binary search, if target data is smaller than current node data, go node.left, otherwise, go node.right.
def search(root, data):
# Base Cases: root is empty or data is present at root
if root is None or root.data == data:
return root if root.data< data:
return search(root.right, data) # data is smaller than root's data
return search(root.left,key)
Insert a node
A new node is always inserted at the leaf.
def insert(root, key):
if root is None:
return Node(key) # if the data is the same, return root (no change)
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
Delete a node
there are three kinds of delete:
- delete a leaf node
- delete a node that only has one child
- delete a node that has two children, need to find the smallest node to replace the deleted position
def min_node(node)
current = node# loop down to find the leftmost leaf
while(current.left is not None):
current = current.left
return currentdef delete(root, data):
# Base Case
if root is None:
return root
if data < root.data:
root.left = delete(root.left, data)
elif data > root.data:
root.right = delete(root.right, data)
# If data is same as root's data, the node should be deleted
else:
# If the node is a leaf node
if root.left is None and root.right is None:
return None
# If one of the children is empty
if root.left is None:
temp = root.right
root = None
return temp
elif root.right is None:
temp = root.left
root = None
return temp
# If node with two children:
# Get the inorder successor
# (smallest in the right subtree)
temp = min_node(root.right)
# Copy the inorder successor's
# content to this node
root.data = temp.data
# Delete the inorder successor
root.right = deleteNode(root.right, temp.data)
return root
Inorder traversal implementing on Binary Search Tree
The problems above seems that can be solved by inorder traversal for the tree. If the result of inorder traversal of the tree is sorted in ascending order, then it is a BST. To find the predecessor and successor, just check the result of inorder traversal of the tree, the predecessor is the previous one of the target key while the next one of the target key is the successor.
