--- title: "Implement BST using doubly linked list" subject: "Data Structure and Algorithm" chapter: 6 key: "semester_4/data_structure_and_algorithm:bst-using-doubly-linked-list" source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/bst-using-doubly-linked-list site: BCT Engineering --- # Implement BST using doubly linked list Data Structure and Algorithm · Chapter 6: Trees - Asked in: 2073 Magh, 6 marks - 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-using-doubly-linked-list - Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-6 ## Question Write an algorithm to implement a Binary Search Tree using doubly linked list. ## Short answer Each BST node has data and two pointers, left and right, forming a doubly linked structure. Insert compares x with current node, goes left if smaller, right if larger, and attaches the new node where a null link is found. Search follows the same path; inorder visits left, root, right. ## Answer A BST node is implemented as a doubly-linked structure: each node holds the data and two pointers, `left` (previous) and `right` (next), pointing to its two children. Together with the root pointer, this represents the whole tree. #### Algorithm ```text Node: info, left, right (both NULL for a new node) Insert(root, x): 1. create node N with info = x, left = right = NULL 2. if root = NULL root = N, stop 3. p = root 4. loop: if x < p->info: if p->left = NULL then p->left = N, stop else p = p->left else if x > p->info: if p->right = NULL then p->right = N, stop else p = p->right else stop (duplicate, discard N) Search(root, x): follow left if x < info, right if x > info, until found or NULL. Inorder(p): if p != NULL: Inorder(p->left); visit p; Inorder(p->right) ``` #### C implementation ```c #include #include struct node { int info; struct node *left, *right; /* two links: doubly linked node */ }; struct node *newnode(int x) { struct node *n = (struct node *)malloc(sizeof(struct node)); n->info = x; n->left = n->right = NULL; return n; } struct node *insert(struct node *root, int x) { struct node *n = newnode(x), *p, *q = NULL; if (root == NULL) return n; /* first node becomes root */ p = root; while (p != NULL) { /* q trails p as its parent */ q = p; if (x < p->info) p = p->left; else if (x > p->info) p = p->right; else { free(n); return root; } /* duplicate */ } if (x < q->info) q->left = n; else q->right = n; return root; } struct node *search(struct node *p, int x) { while (p != NULL && p->info != x) p = (x < p->info) ? p->left : p->right; return p; } void inorder(struct node *p) { if (p != NULL) { inorder(p->left); printf("%d ", p->info); inorder(p->right); } } int main(void) { struct node *root = NULL; int a[] = {50, 30, 70, 20, 40}, i; for (i = 0; i < 5; i++) root = insert(root, a[i]); inorder(root); /* 20 30 40 50 70 */ printf("\n%s\n", search(root, 40) ? "found" : "not found"); return 0; } ``` Output: `20 30 40 50 70` then `found`. Insert and search cost O(h). ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. How is a BST node built with a doubly-linked structure? A. Data plus one next pointer B. Data plus a parent pointer only C. An array of keys D. Data plus two pointers, left and right, to the children Answer: D. The left and right links act like the previous and next links. (Key point: Node structure) 2. In the insert algorithm, if x < p->info what happens? A. Go to p->right B. Go to p->left (or attach there if NULL) C. Discard x D. Replace p->info Answer: B. Smaller keys go left. (Key point: Insert direction) 3. How does the code treat a duplicate key? A. It inserts to the left B. It inserts to the right C. It replaces the old node D. It frees the new node and ignores the key Answer: D. When x equals p->info, the new node is discarded. (Key point: Duplicates) 4. Why does the C insert keep q trailing p? A. To count nodes B. So the new node can be attached to the parent when p becomes NULL C. To free the old node D. To sort the keys Answer: B. When p reaches NULL, q is the parent whose left or right link must be set. (Key point: Trailing pointer q) ## Related in Data Structure and Algorithm - [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 - [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 search with algorithm and example](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abinary-search-algorithm-example) — Data Structure and Algorithm, chapter 8, asked 4× - [Insert and delete kth node in doubly linked list](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Adoubly-insert-delete-kth) — Data Structure and Algorithm, chapter 4, asked 2× - [Doubly vs singly linked list](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Adoubly-vs-singly-linked) — Data Structure and Algorithm, chapter 4, asked 2× - [Delete last node of doubly linked list](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Adelete-end-node-doubly) — Data Structure and Algorithm, chapter 4 ## Related in other subjects - [32:1 MUX tree from 4:1; implement Σ(0,1,3,8,9,13)](https://www.bctengineer.com/question.md?key=semester_3%2Fdigital_logic%3Amux-32to1-tree-function) — Digital Logic, chapter 4 - [32:1 MUX tree; implement Σm(0,1,3,8,9,13,15)](https://www.bctengineer.com/question.md?key=semester_3%2Fdigital_logic%3Amux-32to1-tree-function-15) — Digital Logic, chapter 4 - [Decision tree classifier and Hunt's algorithm](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Adecision-tree-hunt) — Data Mining, chapter 3