Binary Search Tree (BST)

A Binary Search Tree is a fundamental node-based data structure used for fast data storage, retrieval, and sorting. It consists of a root node, where each node can have at most two children (left and right).

         The Golden Rule:

        For any given node, all values in its left subtree must be strictly smaller than
        the node's value, and all values in its right subtree must be greater.
      

Core Operations

1. Search & Insertion

Because of the Golden Rule, searching and inserting in a BST is highly efficient. At each step, you compare the target value with the current node:

If the value is less, move to the left child.
If the value is greater, move to the right child.
Repeat this until you find the value (Search) or reach an empty spot (Insert).

2. Deletion

Removing a node from a BST is more complex than inserting because you must preserve the Golden Rule. There are three distinct cases when deleting a target node:

Case 1: The node is a leaf (no children). Simply remove it from the tree.
Case 2: The node has one child. Remove the node and replace it with its only child.
Case 3: The node has two children. This requires a structural fix. You must find the node's In-order Successor (the smallest value in its right subtree) or In-order Predecessor (the largest value in its left subtree). Copy that successor's value to the target node, and then recursively delete the original successor node.

Tree Traversals

Unlike arrays, there are multiple ways to iterate through a tree depending on the order in which you visit the Root, Left, and Right nodes.

Before exploring the traversal algorithms, it is important to understand how a single node is represented in code. In Python, each node is typically an object containing its value and pointers to its left and right children:

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

1. In-Order Traversal (Left, Root, Right)

This method always visits nodes in ascending, sorted order. It is the most commonly used traversal for BSTs.

Step 1 (Left): The function recursively calls itself on the left child, diving down until it reaches the leftmost leaf (the absolutely smallest value in the tree).
Step 2 (Root): Once the left side is exhausted, it processes (e.g., prints) the current node.
Step 3 (Right): Finally, it moves to the right child and repeats the process.

Why it works: Because a BST stores smaller values on the left and larger on the right, forcing the algorithm to explore Left ➔ Root ➔ Right guarantees we read the data in perfectly sorted order.

def in_order(node):
    if node is not None:
        in_order(node.left)
        print(node.value, end=" ")
        in_order(node.right)

2. Pre-Order Traversal (Root, Left, Right)

This method captures the top-down structure of the tree. It is mainly used for creating a copy of the tree or serializing it to save in a file.

Step 1 (Root): Process the current node immediately upon visiting it, before looking at any children.
Step 2 (Left): Recursively process the entire left subtree.
Step 3 (Right): Recursively process the entire right subtree.

Why it works: By recording the parent before its children, we capture the exact hierarchy. If you insert values into a new, empty tree following a pre-order sequence, you will perfectly recreate the original tree's shape.

def pre_order(node):
    if node is not None:
        print(node.value, end=" ")
        pre_order(node.left)
        pre_order(node.right)

3. Post-Order Traversal (Left, Right, Root)

This method dives all the way down to the leaves and processes nodes from the bottom up. It is strictly used for safely deleting a tree.

Step 1 (Left): Recursively process the entire left subtree.
Step 2 (Right): Recursively process the entire right subtree.
Step 3 (Root): Only after both left and right branches are fully resolved, process the current node.

Why it works: A node is processed only after all of its descendants have been processed. If you are freeing memory (deleting nodes), this ensures you never delete a parent node while it still holds active pointers to its children.

def post_order(node):
    if node is not None:
        post_order(node.left)
        post_order(node.right)
        print(node.value, end=" ")

Quick Comparison Example:
Imagine a simple Binary Search Tree structured like this:

      4
    /   \
   2     6
  / \   / \
 1   3 5   7

Depending on the algorithm you choose, the output sequence will be completely different:

In-Order: 1, 2, 3, 4, 5, 6, 7 (Perfectly sorted)
Pre-Order: 4, 2, 1, 3, 6, 5, 7 (Explores roots before leaves)
Post-Order: 1, 3, 2, 5, 7, 6, 4 (Explores leaves before roots)

The Balancing Problem

The efficiency of a BST depends entirely on its height. If you insert sorted data (e.g., 1, 2, 3, 4, 5) into a standard BST, every new node goes to the right. The tree becomes highly lopsided, effectively degrading into a standard Linked List.

Worst-Case Scenario: In a completely unbalanced tree, you can no longer skip half of the data. Searching for a value forces you to check every single node, causing the time complexity to drop from $O(\log n)$ to $O(n)$.

To prevent this, computer scientists use Self-Balancing Binary Search Trees (like AVL Trees or Red-Black Trees), which automatically rotate their nodes during insertion to keep the tree's height as short as possible.

Complexity Analysis

Operation	Average Case	Worst Case (Unbalanced)
Access / Search	$O(\log n)$	$O(n)$
Insertion	$O(\log n)$	$O(n)$
Deletion	$O(\log n)$	$O(n)$
Space Complexity	$O(n)$	$O(n)$