---
title: "BST insertion algorithm"
subject: "Data Structure and Algorithm"
chapter: 6
key: "semester_4/data_structure_and_algorithm:bst-insertion-algorithm"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/bst-insertion-algorithm
site: BCT Engineering
---

# BST insertion algorithm

Data Structure and Algorithm · Chapter 6: Trees

- Asked in: 2068 Bhadra, 4 marks
- Video: [Binary Search Tree - Insertion Pseudo Code](https://www.youtube.com/watch?v=nVJI8sUlwSs) — Lalitha Natraj
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/bst-insertion-algorithm
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-6

## Question

Write an algorithm for inserting nodes in BST.

## Short answer

Starting at the root, compare the key x with the current node's info. Go left if less, right if greater. When a null link is reached, attach a new leaf node there. Duplicates are ignored; average time O(log n), worst O(n).

## Answer

To insert a key into a BST, search for it from the root. The search ends at a NULL link, and the new node is attached exactly there as a leaf. Duplicates are ignored.

#### Algorithm (iterative)
```text
Insert(root, x)
1. Create a new node N: N->info = x, N->left = N->right = NULL.
2. If root = NULL: root = N; stop.
3. Set p = root.
4. Repeat:
      if x < p->info:
            if p->left = NULL: p->left = N; stop
            else p = p->left
      else if x > p->info:
            if p->right = NULL: p->right = N; stop
            else p = p->right
      else: x is already present; discard N; stop
```

#### Recursive version (C)
```c
struct node *insert(struct node *root, int x) {
    if (root == NULL) {                       /* empty spot found */
        struct node *n = malloc(sizeof(struct node));
        n->info = x; n->left = n->right = NULL;
        return n;
    }
    if (x < root->info)      root->left  = insert(root->left, x);
    else if (x > root->info) root->right = insert(root->right, x);
    return root;                              /* duplicates ignored */
}
```
Example: inserting 50, 30, 70, 20, 40, 60 gives root 50, left child 30 (children 20, 40) and right child 70 (left child 60). To insert 65: 65 > 50 right; 65 < 70 left; 65 > 60 so it becomes the right child of 60.

Time: O(h), i.e. O(log n) on average and O(n) in the worst case.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. Where is a new key attached in a BST?
   A. As the new root
   B. As a parent of the root
   C. As a leaf at the NULL link where search ends
   D. In the middle of the path
   Answer: C. Search from the root until NULL; attach the new node there. (Key point: Insertion position)

2. How does the algorithm handle a key already present?
   A. It is ignored (new node discarded)
   B. Inserted to the left
   C. Inserted to the right twice
   D. The tree is rebuilt
   Answer: A. The algorithm stops without changing the tree. (Key point: Duplicates)

3. In the example, where does 65 go?
   A. Left child of 60
   B. Left child of 70
   C. Right child of 60
   D. Right child of 70
   Answer: C. 65 > 50 right; 65 < 70 left; 65 > 60 right of 60. (Key point: Example)

4. What is the time of insertion?
   A. O(h): O(log n) on average, O(n) in the worst case
   B. O(1) always
   C. O(n log n)
   D. O(log n) always
   Answer: A. Insert follows one root-to-leaf path, so cost depends on tree height. (Key point: Complexity)

## Related in Data Structure and Algorithm

- [B-tree insertion algorithm; AVL of months](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abtree-insertion-avl-months) — Data Structure and Algorithm, chapter 6, asked 2×
- [Preorder and postorder of a BST](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abst-preorder-postorder-52-38) — Data Structure and Algorithm, chapter 6
- [Strictly binary tree has 2n-1 nodes](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Astrict-binary-tree-nodes-proof) — Data Structure and Algorithm, chapter 6
- [Delete BST node with one child](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abst-delete-one-child) — Data Structure and Algorithm, chapter 6
- [BST properties and recursive search](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abst-properties-recursive-search) — Data Structure and Algorithm, chapter 6
- [Binary tree traversals; preorder of BST](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abinary-tree-traversal-methods-preorder) — Data Structure and Algorithm, chapter 6

## Related in other subjects

- [Short note: LNA cavity device / insertion loss](https://www.bctengineer.com/question.md?key=semester_7%2Frf_and_microwave_engineering%3Alna-insertion-loss-note) — RF and Microwave Engineering, chapter 6