Binary Search Tree Operations
Traverse
100%
Ctrl + scroll to zoom
Binary Search Tree
Insert, search, and delete nodes in a BST - see the tree rebalance visually.
Time O(log n) · Space O(n)
Implementation
from enum import Enum
class TreeNode:
"""A single node in the binary search tree."""
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def __str__(self):
return str(self.val)
def __repr__(self):
return str(self.val)
class UbstTree:
"""
Unbalanced Binary Search Tree implementation.
Provides operations for adding, searching, deleting nodes,
finding successors, and traversing the tree in different orders.
"""
def __init__(self, val):
"""Initialize the tree with a root value."""
self.root = TreeNode(val)
def __contains__(self, val):
"""Allow 'val in tree' syntax."""
return self.search(val) is not None
def add(self, val):
"""Add a value to the tree. Duplicates are ignored."""
def _add(val, cur_node: TreeNode):
if cur_node is None:
return TreeNode(val)
if cur_node.val == val:
return cur_node
elif val < cur_node.val:
cur_node.left = _add(val, cur_node.left)
elif cur_node.val < val:
cur_node.right = _add(val, cur_node.right)
return cur_node
self.root = _add(val, self.root)
def search(self, val):
"""
Search for a value in the tree.
Returns the node if found, None otherwise.
"""
def _search(val, cur_node: TreeNode):
if cur_node is None:
return None
if val < cur_node.val:
return _search(val, cur_node.left)
elif cur_node.val < val:
return _search(val, cur_node.right)
else:
return cur_node
return _search(val, self.root)
def delete(self, val):
"""
Delete a value from the tree.
Handles three cases: no children, one child, two children.
"""
if not self.root:
return
def _delete_node(cur_node: TreeNode, val_to_delete):
if cur_node is None:
return None
if val_to_delete < cur_node.val:
cur_node.left = _delete_node(cur_node.left, val_to_delete)
return cur_node
elif cur_node.val < val_to_delete:
cur_node.right = _delete_node(cur_node.right, val_to_delete)
return cur_node
else: # cur_node.val == val_to_delete
if cur_node.left and cur_node.right:
# 2 children
successor = self.find_successor(cur_node)
cur_node.val = successor.val
cur_node.right = _delete_node(cur_node.right, successor.val)
return cur_node
elif cur_node.left:
# only left child
return cur_node.left
elif cur_node.right:
# only right child
return cur_node.right
else:
# no children
return None
self.root = _delete_node(self.root, val)
def find_successor(self, node: TreeNode):
"""
Find the in-order successor of a node.
If node has right subtree: successor is the leftmost node in right subtree.
Otherwise: successor is the first ancestor where node is in left subtree.
"""
if node.right:
# find leftmost child of right subtree
leftmost_child_right_subtree = node.right
while leftmost_child_right_subtree.left:
leftmost_child_right_subtree = leftmost_child_right_subtree.left
return leftmost_child_right_subtree
else:
# find the first ancestor for which the node is in the left subtree
successor = None
current = self.root
while current:
if current.val < node.val:
current = current.right
elif node.val < current.val:
successor = current
current = current.left
else:
break
return successor
class TraverseOrder(Enum):
"""Enumeration of tree traversal orders."""
preorder = 1
inorder = 2
postorder = 3
def traverse(self, type: TraverseOrder):
"""
Traverse the tree in the specified order.
Returns a list of values.
"""
arr = []
def _postorder(root: TreeNode):
if not root:
return
_postorder(root.left)
_postorder(root.right)
arr.append(root.val)
def _inorder(root: TreeNode):
if not root:
return
_inorder(root.left)
arr.append(root.val)
_inorder(root.right)
def _preorder(root: TreeNode):
if not root:
return
arr.append(root.val)
_preorder(root.left)
_preorder(root.right)
if type == UbstTree.TraverseOrder.preorder:
_preorder(self.root)
elif type == UbstTree.TraverseOrder.postorder:
_postorder(self.root)
elif type == UbstTree.TraverseOrder.inorder:
_inorder(self.root)
else:
raise TypeError("Invalid traverse order passed.")
return arr
# Example usage:
if __name__ == "__main__":
tree = UbstTree(10)
tree.add(5)
tree.add(15)
tree.add(3)
tree.add(7)
tree.add(12)
tree.add(18)
# Traverse in different orders
print(tree.traverse(UbstTree.TraverseOrder.preorder)) # [10, 5, 3, 7, 15, 12, 18]
print(tree.traverse(UbstTree.TraverseOrder.inorder)) # [3, 5, 7, 10, 12, 15, 18]
print(tree.traverse(UbstTree.TraverseOrder.postorder)) # [3, 7, 5, 12, 18, 15, 10]
# Search
print(tree.search(12)) # TreeNode with val=12
print(7 in tree) # True
# Delete nodes
tree.delete(7) # no children
tree.delete(10) # 2 children
tree.delete(18) # 1 child
tree.delete(100) # not in tree
About Binary Search Tree
How Binary Search Tree Works
A binary search tree (BST) is an ordered binary tree where each node's left subtree contains only values less than the node, and the right subtree only values greater. This property enables efficient search, insertion, and deletion with O(log n) average time.
To search, compare the target with the current node and go left or right accordingly. To insert, follow the same path until you find an empty spot. To delete, handle three cases: leaf node (remove), one child (replace with child), or two children (replace with in-order successor).
Complexity
- Time
- O(log n)
- Space
- O(n)
When to Use Binary Search Tree
- Dictionary and symbol table implementations
- Database indexing
- Priority-based data management