Binary Search Trees

IB Syllabus: B4.1.4 (HL) – Explain the structures and properties of BSTs: data organization, insert, delete, search, traverse; sketching as tree diagram. (Delete is covered in BST Operations.)

This page is HL only.

Table of Contents

  1. Key Concepts
    1. The BST Property
    2. Tree Terminology
    3. The TreeNode Class
    4. Why BSTs?
  2. Worked Examples
    1. Example 1: BST Insert and In-Order Traversal
    2. Example 2: Search
    3. Example 3: Building a BST from a Sequence
  3. Quick Code Check
  4. Trace Exercise
  5. Code Completion
  6. Spot the Bug
  7. Output Prediction
  8. Practice Exercises
    1. Core
    2. Extension
    3. Challenge
  9. Connections

Key Concepts

A Binary Search Tree (BST) is a hierarchical data structure where each node has at most two children (left and right), and the data is organized so that searching, inserting, and retrieving in sorted order are efficient.

The BST Property

For every node in the tree:

  • All values in the left subtree are less than the node’s value
  • All values in the right subtree are greater than the node’s value

This rule applies recursively to every subtree.

Tree Terminology

Term Meaning
Root The topmost node (no parent)
Parent A node that has one or two children below it
Left child The child with a smaller value
Right child The child with a larger value
Leaf A node with no children (both left and right are null)
Internal node A node that has at least one child
Subtree A node and all its descendants
Height Number of levels from root to the deepest leaf

The TreeNode Class 

public class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;

    public TreeNode(int data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

Each node stores data and two references – one to its left child and one to its right child. Like linked list nodes, tree nodes are self-referential.

Why BSTs?

Structure Search Insert Sorted output
Unsorted array O(n) O(1) O(n log n) sort needed
Sorted array O(log n) binary search O(n) shift elements Already sorted
Linked list O(n) O(1) at head O(n log n) sort needed
BST (balanced) O(log n) O(log n) O(n) in-order traversal

A balanced BST gives O(log n) search AND O(log n) insert – the best of both worlds. In-order traversal produces sorted output without needing a separate sorting step.

Worked Examples

Example 1: BST Insert and In-Order Traversal 

public class BST {
    private TreeNode root;

    public BST() {
        root = null;
    }

    // Insert a value into the BST
    public void insert(int value) {
        root = insertRec(root, value);
    }

    private TreeNode insertRec(TreeNode node, int value) {
        if (node == null) {
            return new TreeNode(value);   // found the spot
        }
        if (value < node.data) {
            node.left = insertRec(node.left, value);
        } else if (value > node.data) {
            node.right = insertRec(node.right, value);
        }
        // duplicate values are ignored
        return node;
    }

    // In-order traversal: Left, Node, Right (produces sorted output)
    public void inOrder() {
        inOrderRec(root);
        System.out.println();
    }

    private void inOrderRec(TreeNode node) {
        if (node == null) {
            return;
        }
        inOrderRec(node.left);
        System.out.print(node.data + " ");
        inOrderRec(node.right);
    }

    public static void main(String[] args) {
        BST tree = new BST();
        tree.insert(45);
        tree.insert(25);
        tree.insert(65);
        tree.insert(15);
        tree.insert(30);
        tree.insert(55);
        tree.insert(75);

        System.out.println("In-order traversal:");
        tree.inOrder();
    }
}

Output:

In-order traversal:
15 25 30 45 55 65 75

The values were inserted in the order 45, 25, 65, 15, 30, 55, 75 but the in-order traversal outputs them sorted. This is the key power of a BST: in-order traversal always produces sorted output.

How insertion builds the tree:

Insert 45:  45 (root)

Insert 25:      45
               /
             25

Insert 65:      45
               / \
             25   65

Insert 15:      45
               / \
             25   65
            /
          15

Insert 30:      45
               / \
             25   65
            / \
          15   30

Insert 55:      45
               / \
             25   65
            / \   /
          15  30 55

Insert 75:      45
               / \
             25   65
            / \   / \
          15  30 55  75

// Search for a value in the BST
public boolean contains(int target) {
    return containsRec(root, target);
}

private boolean containsRec(TreeNode node, int target) {
    if (node == null) {
        return false;          // reached a leaf -- not found
    }
    if (target == node.data) {
        return true;           // found it
    }
    if (target < node.data) {
        return containsRec(node.left, target);   // search left
    } else {
        return containsRec(node.right, target);  // search right
    }
}

public static void main(String[] args) {
    BST tree = new BST();
    tree.insert(45);
    tree.insert(25);
    tree.insert(65);
    tree.insert(15);
    tree.insert(30);

    System.out.println("Contains 30? " + tree.contains(30));
    System.out.println("Contains 40? " + tree.contains(40));
}

Output:

Contains 30? true
Contains 40? false

Search for 30: Start at 45 (30 < 45, go left) -> 25 (30 > 25, go right) -> 30 (found!). Only 3 comparisons instead of checking all 5 nodes.

Search for 40: Start at 45 (go left) -> 25 (go right) -> 30 (go right) -> null (not found). The search eliminates half the remaining tree at each step.

Example 3: Building a BST from a Sequence

The shape of a BST depends on the insertion order. Different orders produce different trees:

public static void main(String[] args) {
    // Balanced insertion order
    BST balanced = new BST();
    int[] order1 = {40, 20, 60, 10, 30, 50, 70};
    for (int v : order1) {
        balanced.insert(v);
    }
    System.out.print("Balanced: ");
    balanced.inOrder();

    // Sorted insertion order (produces a degenerate tree)
    BST skewed = new BST();
    int[] order2 = {10, 20, 30, 40, 50, 60, 70};
    for (int v : order2) {
        skewed.insert(v);
    }
    System.out.print("Skewed:   ");
    skewed.inOrder();
}

Output:

Balanced: 10 20 30 40 50 60 70
Skewed:   10 20 30 40 50 60 70

Both trees produce the same sorted output, but their shapes are very different:

Balanced:        40              Skewed:   10
                / \                          \
              20   60                        20
             / \   / \                         \
           10  30 50  70                       30
                                                 \
                                                 40
                                                   \
                                                   50
                                                     \
                                                     60
                                                       \
                                                       70

A skewed BST is essentially a linked list. Search becomes O(n) instead of O(log n). The BST advantage depends on the tree being reasonably balanced. Inserting sorted data produces the worst case.

Quick Code Check

Q1. In a BST, where are values smaller than the root stored?

Q2. Which traversal visits nodes in sorted (ascending) order in a BST?

Q3. What defines a leaf node in a BST?

Q4. What is the time complexity of searching in a balanced BST with n nodes?

Q5. What happens when you insert values 1, 2, 3, 4, 5 in order into an empty BST?

Trace Exercise

Insert the values 35, 15, 48, 9, 10, 30, 27 into an empty BST (in this order). Fill in where each value is placed.

Insert valueComparison pathPlaced as
35 (empty tree)
15 15 < 35
48 48 > 35
9 9 < 35, 9 < 15
10 right child of 9
30
27 27 < 35, 27 > 15, 27 < 30

Code Completion

Complete the recursive insert method for a BST.

Fill in the blanks:

private TreeNode insertRec(TreeNode node, int value) {
    if (node == ) {
        return new TreeNode(value);
    }
    if (value < node.) {
        node.left = insertRec(node., value);
    } else if (value > node.data) {
        node.right = insertRec(node., value);
    }
    return node;
}

Complete the recursive in-order traversal.

Fill in the blanks for Left-Node-Right order:

private void inOrderRec(TreeNode node) {
    if (node == null) {
        return;
    }
    inOrderRec(node.);
    System.out.print(node.data + " ");
    inOrderRec(node.);
}

Spot the Bug

This insert method builds a tree where in-order traversal produces descending instead of ascending order:

1private TreeNode insertRec(TreeNode node, int value) { 2 if (node == null) { 3 return new TreeNode(value); 4 } 5 if (value > node.data) { 6 node.left = insertRec(node.left, value); 7 } else if (value < node.data) { 8 node.right = insertRec(node.right, value); 9 } 10 return node; 11}

Pick the correct fix for line 5:

This search method never finds values that are in the left subtree:

1private boolean containsRec(TreeNode node, int target) { 2 if (node == null) { 3 return false; 4 } 5 if (target == node.data) return true; 6 if (target < node.data) { 7 return containsRec(node.right, target); 8 } else { 9 return containsRec(node.left, target); 10 } 11}

Pick the correct fix:

Output Prediction

What does this code print?

BST tree = new BST();
tree.insert(50);
tree.insert(30);
tree.insert(70);
tree.insert(20);
tree.insert(40);
tree.inOrder();

Type the exact output:

What does this code print?

BST tree = new BST();
tree.insert(50);
tree.insert(30);
tree.insert(70);
tree.insert(20);
tree.insert(40);
System.out.println(tree.contains(40));
System.out.println(tree.contains(35));

Type the exact output:

Practice Exercises

Core

  1. Build and traverse – Insert the values 35, 15, 48, 9, 10, 30, 27 into an empty BST. Draw the resulting tree on paper. Then run an in-order traversal and verify the output is sorted.
  2. Search trace – Using the tree from exercise 1, trace the comparison path to search for: (a) 30, (b) 27, (c) 50 (not in tree). How many comparisons does each search require?
  3. Different insertion orders – Insert the values 1-7 into a BST in these two orders: (a) 4, 2, 6, 1, 3, 5, 7 and (b) 1, 2, 3, 4, 5, 6, 7. Draw both trees. Which is balanced? Which is skewed?

Extension

  1. Find minimum and maximum – Write methods public int findMin() and public int findMax() that return the smallest and largest values in the BST. (Hint: the smallest value is the leftmost node; the largest is the rightmost.)
  2. Count nodes – Write a recursive method public int size() that returns the total number of nodes in the BST. (Hint: size = 1 + size(left) + size(right), with base case: null returns 0.)

Challenge

  1. Pre-order and post-order – Add preOrder() (Node-Left-Right) and postOrder() (Left-Right-Node) traversal methods to the BST class. Test on the tree from exercise 1. Verify: pre-order starts with the root; post-order ends with the root.
  2. Reconstruct from traversal – Given that the in-order traversal of a BST is 9, 10, 15, 27, 30, 35, 48 and the pre-order traversal is 35, 15, 9, 10, 30, 27, 48, draw the original tree. Explain your reconstruction strategy.

Connections

  • Prerequisites: Recursion – BST operations are naturally recursive
  • Prerequisites: Linked Lists – TreeNode is similar to Node but with two references instead of one
  • Related: Searching Algorithms – BST search is analogous to binary search on a sorted array
  • Next: BST Operations – deletion, tree height, balanced vs unbalanced, all three traversals

© EduCS.me — A resource hub for Computer Science education

This site uses Just the Docs, a documentation theme for Jekyll.