Skip to content

Instantly share code, notes, and snippets.

@ascherj

ascherj/bst.py

Last active July 31, 2025 05:42
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save ascherj/21152c800d892da8a8d5a7a1971df8f5 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save ascherj/21152c800d892da8a8d5a7a1971df8f5 to your computer and use it in GitHub Desktop.
Download ZIP
Binary Search Tree - Node Insertion & Removal Demonstration
Raw
bst.py
class TreeNode:
"""
A node in a Binary Search Tree.
Attributes:
val: The value stored in the node
left: Reference to the left child node
right: Reference to the right child node
"""
def __init__(self, val: int) -> None:
"""
Initialize a new tree node.
Args:
val: The value to store in the node
"""
self.val = val
self.left: TreeNode | None = None
self.right: TreeNode | None = None
def insert(root: TreeNode | None, val: int) -> TreeNode:
"""
Insert a new node into the BST and return the root.
Args:
root: The root node of the BST (can be None for empty tree)
val: The value to insert
Returns:
TreeNode: The root node of the BST after insertion
Time Complexity: O(log n) average, O(n) worst case (unbalanced tree)
Space Complexity: O(log n) average, O(n) worst case (recursion stack)
"""
if not root:
return TreeNode(val)
if val > root.val:
root.right = insert(root.right, val)
elif val < root.val:
root.left = insert(root.left, val)
return root
def minValueNode(root: TreeNode | None) -> TreeNode | None:
"""
Find and return the node with the minimum value in the BST.
Args:
root: The root node of the BST or subtree
Returns:
TreeNode: The node containing the minimum value, or None if tree is empty
Time Complexity: O(log n) average, O(n) worst case (unbalanced tree)
Space Complexity: O(1) - iterative approach uses constant space
"""
curr = root
while curr and curr.left:
curr = curr.left
return curr
def remove(root: TreeNode | None, val: int) -> TreeNode | None:
"""
Remove a node with the given value from the BST and return the root.
Handles three deletion cases:
1. Node with no children (leaf node)
2. Node with one child
3. Node with two children (uses inorder successor)
Args:
root: The root node of the BST (can be None for empty tree)
val: The value to remove from the BST
Returns:
TreeNode: The root node of the BST after removal, or None if tree becomes empty
Time Complexity: O(log n) average, O(n) worst case (unbalanced tree)
Space Complexity: O(log n) average, O(n) worst case (recursion stack)
"""
if not root:
return None
if val > root.val:
root.right = remove(root.right, val)
elif val < root.val:
root.left = remove(root.left, val)
else:
# Node to be deleted found - handle 3 cases:
# Case 1: Node has no left child (0 or 1 child on right)
if not root.left:
return root.right
# Case 2: Node has left child but no right child (1 child on left)
elif not root.right:
return root.left
# Case 3: Node has both left and right children
else:
# Find the inorder successor (smallest value in right subtree)
minNode = minValueNode(root.right)
# Replace current node's value with successor's value
root.val = minNode.val
# Delete the successor from right subtree
root.right = remove(root.right, minNode.val)
return root
def print_tree(root: TreeNode | None, prefix: str = "", is_last: bool = True, is_root: bool = True) -> None:
"""
Print a visual representation of the BST using ASCII art.
Args:
root: The root node of the tree or subtree to print
prefix: String prefix for indentation (used internally for recursion)
is_last: Whether this node is the last child (used internally for recursion)
is_root: Whether this is the root node (used internally for recursion)
Time Complexity: O(n) - visits each node once
Space Complexity: O(h) where h is height (recursion stack)
"""
if not root:
return
if is_root:
print(f"{root.val}")
else:
connector = "└── " if is_last else "├── "
print(prefix + connector + str(root.val))
children = []
if root.right:
children.append((root.right, False))
if root.left:
children.append((root.left, True))
for i, (child, is_left) in enumerate(children):
is_last_child = (i == len(children) - 1)
if is_root:
extension = " "
else:
extension = "│ " if not is_last else " "
print_tree(child, prefix + extension, is_last_child, False)
def inorder_traversal(root: TreeNode | None) -> list[int]:
"""
Perform an inorder traversal of the BST.
Inorder traversal visits nodes in ascending order for a BST:
left subtree -> current node -> right subtree
Args:
root: The root node of the BST
Returns:
list: A list of values in ascending order
Time Complexity: O(n) - visits each node exactly once
Space Complexity: O(n) for result list + O(h) for recursion stack
"""
result = []
def inorder(node):
if node:
inorder(node.left)
result.append(node.val)
inorder(node.right)
inorder(root)
return result
if __name__ == "__main__":
print("=== BST INSERTION AND DELETION DEMONSTRATION ===\n")
# Initialize empty BST
root = None
# INSERTION DEMONSTRATION
print("1. BST INSERTION:")
print("Building BST by inserting values: 50, 30, 20, 40, 70, 60, 80")
values = [50, 30, 20, 40, 70, 60, 80]
for val in values:
root = insert(root, val)
print(f"After inserting {val}:")
print_tree(root)
print(f"Inorder traversal: {inorder_traversal(root)}")
print()
print("=" * 50)
# DELETION DEMONSTRATIONS
print("\n2. BST DELETION - THREE CASES:")
# Case 1: Deleting leaf node (no children)
print("\nCASE 1: Deleting leaf node (no children)")
print("Deleting 20 (leaf node):")
print("Before deletion:")
print_tree(root)
print(f"Inorder: {inorder_traversal(root)}")
root = remove(root, 20)
print("After deleting 20:")
print_tree(root)
print(f"Inorder: {inorder_traversal(root)}")
# Case 2: Deleting node with one child
print("\n" + "=" * 30)
print("\nCASE 2: Deleting node with one child")
print("\nDeleting 30 (has only right child 40):")
print("Before deletion:")
print_tree(root)
print(f"Inorder: {inorder_traversal(root)}")
root = remove(root, 30)
print("After deleting 30:")
print_tree(root)
print(f"Inorder: {inorder_traversal(root)}")
# Case 3: Deleting node with two children
print("\n" + "=" * 30)
print("\nCASE 3: Deleting node with two children")
print("Deleting 50 (root node with both left and right children):")
print("Before deletion:")
print_tree(root)
print(f"Inorder: {inorder_traversal(root)}")
root = remove(root, 50)
print("After deleting 50 (replaced with inorder successor 60):")
print_tree(root)
print(f"Inorder: {inorder_traversal(root)}")
print("\n" + "=" * 50)
print("\nFINAL BST STATE:")
print_tree(root)
print(f"Final inorder traversal: {inorder_traversal(root)}")
# Additional deletions to show more cases
print("\n" + "=" * 30)
print("\nADDITIONAL DELETION EXAMPLES:")
print("\nDeleting 70 (has only left child 80):")
root = remove(root, 70)
print_tree(root)
print(f"Inorder: {inorder_traversal(root)}")
print("\nDeleting 40 (leaf node):")
root = remove(root, 40)
print_tree(root)
print(f"Final inorder: {inorder_traversal(root)}")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment