← Computer Science blog
Concept guide9 October 2026 · 3 min read

Binary Search Tree: Insertion, Traversals and Deletion, Worked by Hand

CSEITAI&DSBCABSc CSBSc ITCOIT

A binary search tree (BST) has one rule: for every node, everything in its left subtree is smaller and everything in its right subtree is larger. Every operation is just that rule applied again and again.

Insertion: follow the rule until you find an empty spot

Insert these values in this order: 50, 30, 70, 20, 40, 60, 80.

  • 50 becomes the root.
  • 30 < 50, so it goes left of 50.
  • 70 > 50, so it goes right of 50.
  • 20 < 50 → left; 20 < 30 → left of 30.
  • 40 < 50 → left; 40 > 30 → right of 30.
  • 60 > 50 → right; 60 < 70 → left of 70.
  • 80 > 50 → right; 80 > 70 → right of 70.

The tree:

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

The order of insertion decides the shape. Insert the same numbers as 20, 30, 40, 50, 60, 70, 80 and you get a tall chain with every node having only a right child, where search degrades from O(log n) to O(n). That is why balanced trees (AVL, red-black) exist.

The three depth-first traversals

All three visit every node. They differ only in when the node itself is visited relative to its two subtrees.

TraversalOrderResult for our tree
InorderLeft, Node, Right20 30 40 50 60 70 80
PreorderNode, Left, Right50 30 20 40 70 60 80
PostorderLeft, Right, Node20 40 30 60 80 70 50

Two facts worth stating in a viva:

  1. Inorder traversal of a BST always gives sorted output. That is a direct consequence of the BST rule, and it is how you verify a tree is a valid BST.
  2. Preorder is how you copy a tree (you must create the parent before its children). Postorder is how you delete one (you must free the children before the parent).

Search

To search for 60: start at 50, 60 > 50 so go right; at 70, 60 < 70 so go left; found. Each step discards one whole subtree, which is why a balanced BST searches in O(log n).

Deletion: three cases

Case 1: the node is a leaf

Delete 20. It has no children, so simply remove it. Node 30 now has only a right child (40).

Case 2: the node has one child

Delete 30 (now that 20 is gone, it has only the right child 40). Replace 30 by its child 40:

          50
        /    \
      40      70
             /  \
           60    80

Case 3: the node has two children

Delete 70 from the tree above. It has children 60 and 80. You cannot just remove it, so:

  1. Find its inorder successor: the smallest value in the right subtree. That is 80 (leftmost node of the right subtree).
  2. Copy 80 into the node being deleted.
  3. Delete the original 80 node (a leaf, so Case 1).

Result:

          50
        /    \
      40      80
             /
           60

You could equally use the inorder predecessor (the largest value in the left subtree, here 60). Both keep the BST rule intact, and examiners accept either if you state which one you use.

Complexity

OperationBalanced treeWorst case (chain)
SearchO(log n)O(n)
InsertO(log n)O(n)
DeleteO(log n)O(n)

Checklist for exam answers

  1. Draw the tree after each insertion, or at least the final tree clearly.
  2. Write all three traversals if asked, and check inorder is sorted.
  3. For deletion, name the case (leaf, one child, two children) and say whether you used the successor or the predecessor.

Sumantrak™ is an AI mentor built for Indian engineering, diploma, BCA and BSc CS/IT students — Data Structures, Algorithms, and the rest of your syllabus, explained like this. Free to start →