Properties of BSTs

Visualisations: Insert, Remove, Search, Traverse

Before we delve into the algorithmic content, use the visualisation tool below. Explore what a BST looks like (conceptually), insert new items (and duplicate items), remove items, and traverse the tree in different ways.

• BST Visualisations (opens in a new tab)

Overview: BST Properties

• Ordered structure: left child < parent < right child.
• Dynamic: grows and shrinks with insertions/deletions.
• Efficient lookup: average O(log n) search, worst-case O(n) if unbalanced.
• Traversal: in-order results in sorted sequence; pre/post-order for other applications.

BST Structure & Sample Insertions

A Binary Search Tree organises data so that for any node:

• left subtree contains values < node.value
• right subtree contains values > node.value

Suppose we insert the sequence [50, 30, 70, 20, 40, 60, 80] into an empty BST:

• 50 becomes the root.
• 30 < 50 → goes to root.left
• 70 > 50 → goes to root.right.
• 20 < 50, < 30 → goes to 30.left
• 40 < 50, > 30 → goes to 30.right
• 60 > 50, < 70 → goes to 70.left
• 80 > 50, > 70 → goes to 70.right

Diagram after all insertions:

         50
        /  \
      30    70
     /  \  /  \
   20   40 60  80

Deep Dive: Pseudocode

Insert a Value

Begin at the current node (initially the root). Compare the new value to node.value:

• If node is null, you’ve found the insertion point: create and return a new node.
• If value < node.value, recurse into node.left and assign its result back to node.left.
• Otherwise (>=), recurse into node.right and assign its result back to node.right.

Each recursion returns the (possibly new) subtree root so that parent links remain correct.

function insert(node, value):
    if node is null:
        return new Node(value)         // insert new leaf here
    if value < node.value:
        node.left  = insert(node.left, value)  
    else:
        node.right = insert(node.right, value)
    return node                       // link subtree back
    

Search for a Value

Start at the current node (initially the root). Compare the target to node.value:

• If node is null or node.value == target, return node (found or not present).
• If target < node.value, recurse into node.left and return that result.
• Otherwise (target > node.value), recurse into node.right and return that result.

Each recursion bubbles the found node (or null) back up to the caller.

function search(node, target):
    if node is null or node.value == target:
        return node
    if target < node.value:
        return search(node.left, target)
    else:
        return search(node.right, target)
    

Delete a Value

Begin at the current node (initially the root). Compare the value to node.value:

• If node is null, return null (value not found).
• If value < node.value, recurse into node.left and assign its result back to node.left.
• If value > node.value, recurse into node.right and assign its result back to node.right.
• Otherwise you’ve found the node to remove:
  • No children: return null.
  • One child: return that child to take this node’s place.
  • Two children:
    1. Find the in-order successor via findMin(node.right).
    2. Copy its value into this node.
    3. Recursively delete the successor from node.right.

Each recursion returns the (potentially updated) subtree root so parent pointers remain correct.

function delete(node, value):
    if node is null:
        return null
    if value < node.value:
        node.left  = delete(node.left, value)
    else if value > node.value:
        node.right = delete(node.right, value)
    else:
        // removal cases
        if node.left is null:
            return node.right
        if node.right is null:
            return node.left
        successor   = findMin(node.right)
        node.value  = successor.value
        node.right  = delete(node.right, successor.value)
    return node

function findMin(node):
    while node.left is not null:
        node = node.left
    return node
    

Tree Traversals

Pre-Order (N → L → R)

Visit the Node, then recursively traverse Left, then Right. Useful for copying the tree or prefix notation.

function preorder(node):
    if node is null: return
    visit(node.value)
    preorder(node.left)
    preorder(node.right)
    

For our sample tree: [50, 30, 20, 40, 70, 60, 80]

In-Order (L → N → R)

Recursively traverse Left, visit the Node, then Right. Visits the values in sorted (ascending) order.

function inorder(node):
    if node is null: return
    inorder(node.left)
    visit(node.value)
    inorder(node.right)
    

For our sample tree: [20, 30, 40, 50, 60, 70, 80]

Post-Order (L → R → N)

Recursively traverse Left, then Right, then visit the Node. Useful for deleting the tree or postfix notation.

function postorder(node):
    if node is null: return
    postorder(node.left)
    postorder(node.right)
    visit(node.value)
    

For our sample tree: [20, 40, 30, 60, 80, 70, 50]

Scenarios & Applications

Dictionary Lookup

A digital dictionary stores thousands of words that users search by prefix or exact match. A BST organises entries so that each lookup, whether for spellcheck suggestions or autocomplete, descends left or right based on character codes, achieving average O(log n) search time and returning results far faster than scanning an array.

Database Indexing

Relational databases use BST-based structures (e.g. B-trees) to index columns for efficient range queries. In-order traversal of the BST results in sorted records within a key range, enabling rapid retrieval of all entries between two values without full-table scans.

Event Scheduling

An event scheduler maintains future tasks timestamped for execution. Inserting each event into a BST keyed by time ensures the next imminent task is always at the leftmost node, and deletion of executed events adjusts the tree in O(log n), keeping the schedule dynamic and responsive.

Example: BST in Python & Java

• Python
• Java

# Node class for BST elements
class Node:
    def __init__(self, value):
        self.value = value      # node’s key
        self.left  = None       # left child pointer
        self.right = None       # right child pointer

# Binary Search Tree implementation
class BST:
    def __init__(self):
        self.root = None        # tree root

    def insert(self, value):
        # public insert entry point
        self.root = self._insert(self.root, value)

    def _insert(self, node, value):
        # recursive insertion
        if node is None:
            return Node(value)  # create new leaf
        if value < node.value:
            node.left  = self._insert(node.left, value)
        else:
            node.right = self._insert(node.right, value)
        return node

    def search(self, target):
        # start recursive search
        return self._search(self.root, target)

    def _search(self, node, target):
        # found or reached end
        if node is None or node.value == target:
            return node
        if target < node.value:
            return self._search(node.left, target)
        return self._search(node.right, target)

    def delete(self, value):
        # public delete entry point
        self.root = self._delete(self.root, value)

    def _delete(self, node, value):
        # recursive deletion
        if node is None:
            return None
        if value < node.value:
            node.left = self._delete(node.left, value)
        elif value > node.value:
            node.right = self._delete(node.right, value)
        else:
            # remove this node
            if node.left is None:
                return node.right      # no left child
            if node.right is None:
                return node.left       # no right child
            # two children: replace with in-order successor
            succ = self._find_min(node.right)
            node.value = succ.value   # swap values
            node.right = self._delete(node.right, succ.value)
        return node

    def _find_min(self, node):
        # find leftmost node
        while node.left:
            node = node.left
        return node

    def inorder(self):
        # return sorted values via in-order traversal
        result = []
        def _inorder(n):
            if not n:
                return
            _inorder(n.left)
            result.append(n.value)
            _inorder(n.right)
        _inorder(self.root)
        return result

# Demonstration of BST operations
if __name__ == "__main__":
    bst = BST()
    for val in [50, 30, 70, 20, 40, 60, 80]:
        bst.insert(val)
    print("In-order traversal:", bst.inorder())
    node = bst.search(60)
    print("Search for 60:", node.value if node else "Not found")
    bst.delete(70)
    print("After deleting 70:", bst.inorder())

// Node class representing each BST element
class Node {
    int value;      // node’s key
    Node left;      // left child pointer
    Node right;     // right child pointer

    Node(int v) {
        value = v;
        left = right = null;
    }
}

// Binary Search Tree implementation
public class BST {
    private Node root;  // tree root

    // Public insert method
    public void insert(int value) {
        root = insertRec(root, value);
    }

    // Recursive insertion helper
    private Node insertRec(Node node, int value) {
        if (node == null) {
            return new Node(value);  // create new leaf
        }
        if (value < node.value) {
            node.left = insertRec(node.left, value);
        } else {
            node.right = insertRec(node.right, value);
        }
        return node;
    }

    // Public search method
    public Node search(int target) {
        return searchRec(root, target);
    }

    // Recursive search helper
    private Node searchRec(Node node, int target) {
        if (node == null || node.value == target) {
            return node;             // found or reached end
        }
        if (target < node.value) {
            return searchRec(node.left, target);
        }
        return searchRec(node.right, target);
    }

    // Public delete method
    public void delete(int value) {
        root = deleteRec(root, value);
    }

    // Recursive deletion helper
    private Node deleteRec(Node node, int value) {
        if (node == null) {
            return null;
        }
        if (value < node.value) {
            node.left = deleteRec(node.left, value);
        } else if (value > node.value) {
            node.right = deleteRec(node.right, value);
        } else {
            // removal of this node
            if (node.left == null) {
                return node.right;     // no left child
            }
            if (node.right == null) {
                return node.left;      // no right child
            }
            // two children: find in-order successor
            Node succ = findMin(node.right);
            node.value = succ.value;  // swap values
            node.right = deleteRec(node.right, succ.value);
        }
        return node;
    }

    // Find the smallest value in subtree
    private Node findMin(Node node) {
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }

    // In-order traversal printing sorted values
    public void inorder() {
        inorderRec(root);
        System.out.println();
    }

    private void inorderRec(Node node) {
        if (node != null) {
            inorderRec(node.left);
            System.out.print(node.value + " ");
            inorderRec(node.right);
        }
    }

    // Main method demonstrating BST operations
    public static void main(String[] args) {
        BST bst = new BST();
        int[] values = {50, 30, 70, 20, 40, 60, 80};
        for (int v : values) {
            bst.insert(v);
        }
        System.out.print("In-order traversal: ");
        bst.inorder();

        Node found = bst.search(60);
        System.out.println("Search for 60: " + (found != null ? found.value : "Not found"));

        bst.delete(70);
        System.out.print("After deleting 70: ");
        bst.inorder();
    }
}