BST Operations

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

This page is HL only.

Key Concepts

In Binary Search Trees you learned to insert, search, and traverse a BST in-order. This page covers the remaining operations: deletion (the trickiest BST operation), tree height, balanced vs unbalanced trees, and the pre-order and post-order traversals.

Deleting from a BST

Deletion is more complex than insertion because removing a node must preserve the BST property. There are three cases, depending on how many children the node has:

Case Children Strategy
Case 1: Leaf 0 Simply remove the node (set its parent’s reference to null)
Case 2: One child 1 Replace the node with its single child
Case 3: Two children 2 Replace the node’s value with its in-order successor (the smallest value in the right subtree), then delete that successor node

The in-order successor is the leftmost node in the right subtree. It is always greater than everything in the left subtree and less than everything else in the right subtree, making it a valid replacement.

Tree Height

The height of a tree is the number of edges on the longest path from the root to a leaf. An empty tree (null) has height -1, and a single node has height 0.

Height = 1 + max(height(left), height(right))

Height determines worst-case search time: searching a BST takes at most (height + 1) comparisons.

Balanced vs Unbalanced

Property Balanced BST Unbalanced (skewed) BST
Height O(log n) O(n)
Search O(log n) O(n)
Insert O(log n) O(n)
Delete O(log n) O(n)
Shape Roughly symmetric Leans to one side

A BST becomes unbalanced when data is inserted in sorted (or nearly sorted) order. Self-balancing trees (AVL, Red-Black) fix this automatically, but they are beyond the IB syllabus.

Three Traversal Orders

Each traversal visits every node exactly once but in a different order. The name tells you when the node itself is processed:

Traversal Order Mnemonic Use case
Pre-order Node, Left, Right Pre = node first Copying/serializing a tree
In-order Left, Node, Right In = node in the middle Sorted output
Post-order Left, Right, Node Post = node last Deleting a tree, evaluating expressions

Memory aid: The prefix tells you where the Node goes. Pre-order = Node is first. In-order = Node is in the middle. Post-order = Node is last.

Worked Examples

All examples use the TreeNode and BST classes from Binary Search Trees. The TreeNode class stores int data, TreeNode left, and TreeNode right.

Example 1: Deleting from a BST 

// Add to the BST class from the previous page

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

private TreeNode deleteRec(TreeNode node, int value) {
    if (node == null) {
        return null;                     // value not found
    }

    if (value < node.data) {
        node.left = deleteRec(node.left, value);
    } else if (value > node.data) {
        node.right = deleteRec(node.right, value);
    } else {
        // Found the node to delete

        // Case 1: Leaf node (no children)
        if (node.left == null && node.right == null) {
            return null;
        }
        // Case 2: One child
        if (node.left == null) {
            return node.right;           // replace with right child
        }
        if (node.right == null) {
            return node.left;            // replace with left child
        }
        // Case 3: Two children
        // Find the in-order successor (smallest in right subtree)
        int successor = findMin(node.right);
        node.data = successor;           // copy successor value
        // Delete the successor from the right subtree
        node.right = deleteRec(node.right, successor);
    }
    return node;
}

private int findMin(TreeNode node) {
    while (node.left != null) {
        node = node.left;
    }
    return node.data;
}

Walking through the three cases on this tree:

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

Case 1 – Delete 10 (leaf): 10 has no children. Set 20’s left to null.

        40
       / \
     20    60
      \   / \
      30 50  70

Case 2 – Delete 20 (one child): 20 has only a right child (30). Replace 20 with 30.

        40
       / \
     30    60
          / \
        50   70

Case 3 – Delete 40 (two children): 40 has both children. The in-order successor is 50 (the smallest value in the right subtree). Copy 50 into the root, then delete the original 50 node from the right subtree.

        50
       / \
     30    60
             \
             70

Example 2: Pre-Order and Post-Order Traversals 

// Add to the BST class

// Pre-order: Node, Left, Right
public void preOrder() {
    preOrderRec(root);
    System.out.println();
}

private void preOrderRec(TreeNode node) {
    if (node == null) {
        return;
    }
    System.out.print(node.data + " ");   // process Node first
    preOrderRec(node.left);              // then Left
    preOrderRec(node.right);             // then Right
}

// Post-order: Left, Right, Node
public void postOrder() {
    postOrderRec(root);
    System.out.println();
}

private void postOrderRec(TreeNode node) {
    if (node == null) {
        return;
    }
    postOrderRec(node.left);             // Left first
    postOrderRec(node.right);            // then Right
    System.out.print(node.data + " ");   // process Node last
}

Testing on this tree:

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

public static void main(String[] args) {
    BST tree = new BST();
    int[] values = {40, 20, 60, 10, 30, 50, 70};
    for (int v : values) {
        tree.insert(v);
    }

    System.out.print("In-order:   ");
    tree.inOrder();
    System.out.print("Pre-order:  ");
    tree.preOrder();
    System.out.print("Post-order: ");
    tree.postOrder();
}

Output:

In-order:   10 20 30 40 50 60 70
Pre-order:  40 20 10 30 60 50 70
Post-order: 10 30 20 50 70 60 40

Notice: pre-order always starts with the root. Post-order always ends with the root. In-order produces sorted output.

Example 3: Tree Height 

// Add to the BST class

public int height() {
    return heightRec(root);
}

private int heightRec(TreeNode node) {
    if (node == null) {
        return -1;                       // empty tree has height -1
    }
    int leftHeight = heightRec(node.left);
    int rightHeight = heightRec(node.right);
    return 1 + Math.max(leftHeight, rightHeight);
}

public static void main(String[] args) {
    // Balanced tree
    BST balanced = new BST();
    int[] vals1 = {40, 20, 60, 10, 30, 50, 70};
    for (int v : vals1) {
        balanced.insert(v);
    }
    System.out.println("Balanced height: " + balanced.height());

    // Skewed tree
    BST skewed = new BST();
    int[] vals2 = {10, 20, 30, 40, 50};
    for (int v : vals2) {
        skewed.insert(v);
    }
    System.out.println("Skewed height: " + skewed.height());
}

Output:

Balanced height: 2
Skewed height: 4

The balanced tree with 7 nodes has height 2 (3 levels). The skewed tree with 5 nodes has height 4 (5 levels – essentially a linked list). The balanced tree can be searched in at most 3 comparisons; the skewed tree needs up to 5.

Quick Code Check

Q1. When deleting a node that has two children, what value replaces it?

Q2. In a pre-order traversal, which node is visited first?

Q3. In a post-order traversal, which node is visited last?

Q4. What is the height of a balanced BST containing 15 nodes?

Q5. What happens when you delete a leaf node from a BST?

Trace Exercise

Given this BST, trace the three traversal orders.

        30
       / \
     15    45
    / \      \
   8   22    50
TraversalOrder ruleOutput sequence
In-order Left, Node, Right
Pre-order Node, Left, Right
Post-order Left, Right, Node

Trace the deletion of 30 from this BST (Case 3 – two children). Show the tree state after each step.

StepActionResult
1 Node 30 has two children. Find in-order successor. Successor =
2 Copy successor value into node 30's position. Root value becomes
3 Delete the original successor node from the right subtree. Node 45 in right subtree was a case (it has one child: 50)
4 Final tree root with left child 15, right child

Code Completion

Complete the delete method. This code finds the in-order successor and uses it to replace a node with two children.

Fill in the blanks for the two-children case:

// Case 3: node has two children
// Find smallest value in right subtree
int successor = findMin(node.);
// Copy successor value into this node
node. = successor;
// Delete the successor from the right subtree
node.right = deleteRec(node.right, );

Complete the recursive height method.

Fill in the blanks:

private int heightRec(TreeNode node) {
    if (node == ) {
        return -1;
    }
    int leftHeight = heightRec(node.left);
    int rightHeight = heightRec(node.right);
    return 1 + Math.(leftHeight, rightHeight);
}

Spot the Bug

This findMin helper is used during deletion to find the in-order successor, but it returns the wrong value:

1// Find the smallest value in a subtree 2private int findMin(TreeNode node) { 3 while (node.right != null) { 4 node = node.right; 5 } 6 return node.data; 7}

Pick the correct fix:

This traversal is supposed to be post-order (Left, Right, Node) but it prints in the wrong order:

1private void postOrderRec(TreeNode node) { 2 if (node == null) return; 3 postOrderRec(node.left); 4 System.out.print(node.data + " "); 5 postOrderRec(node.right); 6}

Pick the correct fix:

Output Prediction

A BST is built by inserting 25, 10, 35, 5, 18, 42 (in that order). What does preOrder() print?

BST tree = new BST();
int[] vals = {25, 10, 35, 5, 18, 42};
for (int v : vals) {
    tree.insert(v);
}
tree.preOrder();

Type the exact output:

Using the same tree (insert 25, 10, 35, 5, 18, 42), what does postOrder() print?

BST tree = new BST();
int[] vals = {25, 10, 35, 5, 18, 42};
for (int v : vals) {
    tree.insert(v);
}
tree.postOrder();

Type the exact output:

Practice Exercises

Core

  1. Trace all three traversals – Draw this BST on paper, then write out the in-order, pre-order, and post-order traversals: insert 50, 25, 75, 12, 37, 62, 87 into an empty BST.
  2. Delete a leaf – Using the tree from exercise 1, delete 12 (a leaf). Draw the resulting tree. Which deletion case applies?
  3. Delete with one child – From the original tree, delete 75 after first deleting 87 (so 75 has only one child, 62). Draw the resulting tree.

Extension

  1. Delete with two children – From the original tree (exercise 1), delete 25 (two children: 12 and 37). What is the in-order successor? Draw the tree after deletion. Then run an in-order traversal to verify the output is still sorted.
  2. Calculate heights – Write a height() method and test it on: (a) a balanced tree from inserting {40, 20, 60, 10, 30, 50, 70}, and (b) a skewed tree from inserting {10, 20, 30, 40, 50}. Verify your results match the formula.
  3. Count nodes at each level – Write a method public int countAtLevel(int level) that counts how many nodes are at a given level (root is level 0). Test on the tree from exercise 1.

Challenge

  1. Reconstruct from traversals – You are given: pre-order = 50 25 12 37 75 62 87 and in-order = 12 25 37 50 62 75 87. Reconstruct the original tree on paper. Explain your strategy. (Hint: the first value in pre-order is always the root; find it in in-order to determine left and right subtrees.)
  2. Delete the root repeatedly – Starting with the tree from exercise 1, delete the root node three times in a row. After each deletion, write the new root and run an in-order traversal. Verify the sorted order is preserved each time.

Connections

  • Prerequisites: Binary Search Trees – insert, search, in-order traversal, TreeNode class
  • Prerequisites: Recursion – all BST operations use recursive thinking
  • Related: Searching Algorithms – BST search mirrors binary search on sorted arrays
  • Related: Linked Lists – deletion edge cases (preserving references) apply to both structures
  • Next: Sets and HashMaps – different ADTs with different trade-offs

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

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