Binary Search Tree Exam Questions: Insert, Delete, Traverse

A binary search tree (BST) is a data structure that keeps data sorted while you insert and delete, and performs search, insert and delete in O(log n) steps as long as it stays balanced. In a data structures midterm or final it is the topic with the most drawing questions: "insert these keys, delete that one, draw the tree, give the preorder". In this post I keep the rules short and put the weight on questions solved by hand. Every tree and every traversal result was checked both by hand and by running the code below.

The BST Property

The rule holds for every node: all keys in the left subtree are smaller than the node's key, and all keys in the right subtree are larger. It applies to the whole subtree, not only to the direct children; that distinction comes back in Question 6. The tree I use throughout the post results from inserting 50, 30, 70, 20, 40, 60, 80 in this order:

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

What happens to equal keys depends on the course (rejected, sent to the right, or counted). In this post equal keys are not inserted; in an exam, use your lecturer's rule.

Node, Insert and Search

A node is an ordinary class; if you want to refresh how classes and references work, see C# classes and objects.

public class Node
{
    public int Key;
    public Node? Left, Right;
    public Node(int key) => Key = key;
}

public static class Bst
{
    public static Node Insert(Node? node, int key)
    {
        if (node == null) return new Node(key);
        if (key < node.Key) node.Left = Insert(node.Left, key);
        else if (key > node.Key) node.Right = Insert(node.Right, key);
        return node; // equal key: not inserted
    }

    public static bool Search(Node? node, int key)
    {
        while (node != null)
        {
            if (key == node.Key) return true;
            node = key < node.Key ? node.Left : node.Right;
        }
        return false;
    }
}

Both insert and search start at the root and go left if the key is smaller, right if it is larger. A new key is always added as a leaf; existing nodes never move. Usage: Node? root = null; root = Bst.Insert(root, 50);.

Delete: Three Cases

1. Leaf node: remove it directly.
2. Node with one child: the child takes the place of the deleted node.
3. Node with two children: replace the node's key with its inorder successor (the minimum of the right subtree), then delete the successor from the right subtree. The successor cannot have a left child, so this second deletion always falls into case 1 or 2.

// inside the Bst class
public static Node? Delete(Node? node, int key)
{
    if (node == null) return null;
    if (key < node.Key) node.Left = Delete(node.Left, key);
    else if (key > node.Key) node.Right = Delete(node.Right, key);
    else
    {
        if (node.Left == null) return node.Right;  // leaf, or only a right child
        if (node.Right == null) return node.Left;  // only a left child
        Node successor = node.Right;
        while (successor.Left != null) successor = successor.Left;
        node.Key = successor.Key;
        node.Right = Delete(node.Right, successor.Key);
    }
    return node;
}

Some courses use the inorder predecessor (the maximum of the left subtree) instead of the successor. Both leave a valid BST, but the trees differ; use whichever the question asks for, and if it does not say, state your choice in the answer.

Traversals

// inside the Bst class
public static void Inorder(Node? node, List<int> output)
{
    if (node == null) return;
    Inorder(node.Left, output);
    output.Add(node.Key);        // move this line first for preorder, last for postorder
    Inorder(node.Right, output);
}

public static List<int> LevelOrder(Node? root)
{
    var result = new List<int>();
    if (root == null) return result;
    var queue = new Queue<Node>();
    queue.Enqueue(root);
    while (queue.Count > 0)
    {
        Node current = queue.Dequeue();
        result.Add(current.Key);
        if (current.Left != null) queue.Enqueue(current.Left);
        if (current.Right != null) queue.Enqueue(current.Right);
    }
    return result;
}

Results for the tree above:

Traversal	Order	Result
Inorder	left, root, right	20 30 40 50 60 70 80
Preorder	root, left, right	50 30 20 40 70 60 80
Postorder	left, right, root	20 40 30 60 80 70 50
Level-order	level by level, left to right	50 30 70 20 40 60 80

The inorder traversal of a BST is always sorted; that is the fastest way to check a tree you have drawn in an exam. In preorder the root is always the first element, in postorder always the last.

Height, Balance and the Degenerate Case

Height is the number of edges on the path from the root to the deepest leaf; a single-node tree has height 0 and the empty tree −1. Some courses count nodes instead, which makes every value one larger; check the definition.

// inside the Bst class
public static int Height(Node? node) =>
    node == null ? -1 : 1 + Math.Max(Height(node.Left), Height(node.Right));

Every operation follows a single path down from the root, so the cost is O(h). For a tree with n nodes, h is at least ⌊log₂ n⌋ and at most n − 1. If the keys arrive in sorted order (Question 5) the tree turns into a linked list and the expected O(log n) becomes O(n).

Operation	Average	Worst (degenerate)
Search	O(log n)	O(n)
Insert	O(log n)	O(n)
Delete	O(log n)	O(n)
Minimum / maximum	O(log n)	O(n)
Traversal (any)	O(n)	O(n)
Space	O(n) nodes; O(h) stack when recursive	O(n)

If the notation is unfamiliar, the Big O and time complexity guide explains how to read this table.

Question 1: Insert, Then Delete 30

Question: Insert 50, 30, 70, 20, 40, 60, 80 into an empty BST in this order. Then delete 30 and draw the tree (use the inorder successor).

Solution: 50 becomes the root. 30 < 50 goes left, 70 > 50 goes right. 20: smaller than 50, smaller than 30, so left of 30. 40: smaller than 50, larger than 30, so right of 30. 60 and 80 land left and right of 70 by the same reasoning; the result is the tree at the top of the post.

30 has two children. The successor is the minimum of the right subtree; that subtree consists of 40 only, so the successor is 40. 40 is written in place of 30 and the old leaf 40 is removed:

        50
      /    \
    40      70
   /       /  \
  20      60  80

Check: inorder 20 40 50 60 70 80, sorted. With the predecessor, 20 would replace 30 and 40 would stay as its right child.

Question 2: Write All Four Traversals

Question: Give the inorder, preorder, postorder and level-order traversal of the tree from Question 1 before the deletion.

Solution: Preorder step by step: write the root 50; move to the left subtree: 30, its left 20, its right 40; then the right subtree: 70, 60, 80. Result 50 30 20 40 70 60 80. In postorder each node is written after both of its subtrees: 20 40 30, then 60 80 70, and 50 last. All four results are in the table above.

If the same question is asked for the tree after the deletion: preorder 50 40 20 70 60 80, postorder 20 40 60 80 70 50, level-order 50 40 70 20 60 80.

Question 3: Deleting the Root, Successor with a Child

Question: Insert 65 into the first tree, then delete the root 50.

Solution: 65 > 50 go right, 65 < 70 go left, 65 > 60 go right: it becomes the right child of 60.

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

For the successor of 50 keep going left in the right subtree: 70, then 60; 60 has no left child, so the successor is 60. Write 60 into the root. Now the old node 60 has to go; it has one (right) child, which is case 2: 65 takes its place as the left child of 70.

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

Check: inorder 20 30 40 60 65 70 80. The most common mistake in this question is forgetting 65 and dropping it from the tree.

The same tree shows the other two cases as well: 20 is a leaf and is simply removed. If 60 is deleted (in the tree before 50 was deleted), its only child 65 becomes the left child of 70.

Question 4: Rebuilding a BST from Preorder

Question: Draw the BST whose preorder traversal is 40, 20, 10, 30, 25, 60, 50, 70 and give its postorder.

Solution: The first element of a preorder is the root: 40. Of the rest, the keys smaller than 40 (20, 10, 30, 25) form the left subtree and the larger ones (60, 50, 70) the right subtree. Apply the same rule recursively: on the left the root is 20, the smaller key 10 goes left, the larger ones 30 and 25 go right; there 30 is the root and 25 its left child. On the right the root is 60, with 50 on the left and 70 on the right.

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

Postorder: 10 25 30 20 50 70 60 40. The height is 3. A practical shortcut: inserting the keys into an empty BST in preorder order produces the same tree. For a general binary tree a single traversal is not enough to determine the tree; for a BST it is, because the inorder is already known (the sorted keys).

Question 5: Sorted Insertion and the Degenerate Tree

Question: If 10, 20, 30, 40, 50 are inserted into an empty BST in this order, what is the height? How many comparisons does a search for 50 need? What if the same keys were inserted as 30, 20, 40, 10, 50?

Solution: Every new key is larger than all previous ones and always goes right:

10
  \
   20
     \
      30
        \
         40
           \
            50

The height is 4 (n − 1), and finding 50 compares against 5 nodes; the structure is effectively a linked list. With the second order 30 becomes the root, 20 and 40 its children, and 10 and 50 go below them: height 2, and 3 comparisons for 50 (30, 40, 50). Same key set, different insertion order, different tree. AVL and red-black trees solve this by rebalancing with rotations after each insertion.

Question 6: Is This Tree a BST?

Question: Is the following tree a BST?

        50
      /    \
    30      70
   /  \
  20  55

Solution: No. Comparing each node with its own children shows no problem: 20 < 30 < 55 and 30 < 50 < 70. But 55 sits in the left subtree of 50 and is larger than 50; the rule applies to the whole subtree. Quick check: the inorder 20 30 55 50 70 is not sorted. In code the correct check carries the allowed range down to every node:

// inside the Bst class; call: IsBst(root, long.MinValue, long.MaxValue)
public static bool IsBst(Node? node, long min, long max)
{
    if (node == null) return true;
    if (node.Key <= min || node.Key >= max) return false;
    return IsBst(node.Left, min, node.Key) && IsBst(node.Right, node.Key, max);
}

Question 7: Search Path and Height Bounds

Question: (a) In the 8-node tree from Question 3 (before deleting 50), which nodes are visited when searching for 65 and for 45? (b) What are the minimum and maximum height of a BST with 7 nodes?

Solution (a): For 65: 50, 70, 60, 65 — four comparisons, found. For 45: 50, 30, 40; 40 has no right child, so the search fails after three comparisons. The empty position where a failed search ends is exactly where 45 would be placed if it were inserted.

Solution (b): Minimum 2: a tree of height h holds at most 2^(h+1) − 1 nodes, which for h = 2 is exactly 7 (the tree at the top of the post). Maximum 6: with sorted insertion every node has a single child and the height is n − 1.

When to Use It and When Not To

Choose a BST when the data changes and you also need ordered access: minimum and maximum, all keys in a range, the successor of a key, a sorted listing. If the only question is "is this key present?", a hash table (Dictionary, HashSet) is the better choice with O(1) on average, but it keeps no order. If the data never changes, binary search on a sorted array gives the same O(log n) search with less memory; for the cost of sorting the array once, see the sorting algorithms post.

Writing an unbalanced BST by hand is rarely right in production code; if the input arrives sorted, performance collapses. In .NET, SortedSet<T> and SortedDictionary<TKey, TValue> are built on a balanced binary search tree and guarantee O(log n). The value of a hand-written BST is understanding how those structures work, and that is what the exam measures.

Common Mistakes

1. Not assigning the result of the recursion. If you write Insert(node.Left, key); without assigning the return value to node.Left, the new node is created but never attached to the tree. Symptom: no error, but the tree never grows and the inorder prints only the root.

if (key < node.Key) Insert(node.Left, key);             // WRONG: the new node is lost
if (key < node.Key) node.Left = Insert(node.Left, key); // RIGHT

2. Checking only the children when validating a BST. The tree in Question 6 passes that check but is not a BST. Use the range-carrying IsBst, or check that the inorder is sorted.

3. Forgetting to delete the successor in the two-children case. If the key is copied but the old successor node stays, the same key appears twice in the tree; a repetition such as ... 40 40 ... in the inorder is the sign. If the successor has a right child (Question 3), re-attaching that child is part of this step.

4. Mixing up successor and predecessor. The successor is the leftmost node of the right subtree, the predecessor the rightmost node of the left subtree. "One step right, then left all the way" is worth memorising.

If you want to practise drawing questions on your own course's past papers, the exam support page explains how I work.

Frequently Asked Questions

What is the difference between a BST and a binary tree?

A binary tree only says that every node has at most two children; it puts no rule on the order of the keys. A BST adds the ordering rule: the left subtree holds smaller keys and the right subtree larger ones.

Should I use the successor or the predecessor when deleting a node with two children?

Both are correct and leave a valid BST, but the resulting trees differ. In an exam, use the method from your course; if none is specified, state which one you chose.

Can the same key be inserted twice into a BST?

It depends on the definition. Common options are rejecting the insert, consistently sending equal keys to the right subtree, or keeping a counter in the node. Whichever you choose, search and delete have to follow the same rule.

What is the difference between an AVL tree and a BST?

An AVL tree is a BST that keeps the height difference between the left and right subtree of every node at 1 or less. It rebalances itself with rotations after insertions and deletions and therefore guarantees O(log n) in the worst case too.