--- title: "Delete BST node with one child" subject: "Data Structure and Algorithm" chapter: 6 key: "semester_4/data_structure_and_algorithm:bst-delete-one-child" source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/bst-delete-one-child site: BCT Engineering --- # Delete BST node with one child Data Structure and Algorithm · Chapter 6: Trees - Asked in: 2075 Baisakh, 5 marks - Video: [Delete a node from Binary Search Tree](https://www.youtube.com/watch?v=gcULXE7ViZw) — mycodeschool - 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-delete-one-child - Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-6 ## Question Explain deletion of node with one child in BST with suitable example. ## Short answer To delete a node with one child, bypass the node by linking its parent to the child. For example, deleting 18 with left child 13: parent 10 now points to 13. This preserves BST order. ## Answer **Rule:** if the node to be deleted has exactly one child, the node is removed and its only child (with the whole subtree below it) takes its place by linking the child directly to the deleted node's parent. The BST property is preserved because the child subtree already lies in the correct range for that position. #### Steps 1. Search for the node *X* (and keep a pointer to its parent *P*). 2. Let *C* be the only child of *X* (left or right). 3. If *X* is the root, make *C* the new root. 4. Else if *X* is the left child of *P*, set `P->left = C`; otherwise set `P->right = C`. 5. Free *X*. #### Example Delete 18 from the BST (18 has only a left child 13): ```text Before: After: 20 20 / \ / \ 10 47 10 47 / \ / \ 4 18 <- delete 4 13 / 13 ``` Parent 10 now points to 13 instead of 18. In-order traversal before: 4 10 13 18 20 47; after: 4 10 13 20 47, still sorted. #### Code ```c struct node { int info; struct node *left, *right; }; struct node *delete_one_child(struct node *root, int key) { struct node *p = NULL, *x = root, *c; while (x != NULL && x->info != key) { /* find x and its parent */ p = x; x = (key < x->info) ? x->left : x->right; } if (x == NULL) return root; /* key not found */ c = (x->left != NULL) ? x->left : x->right; /* the only child */ if (p == NULL) root = c; /* deleting the root */ else if (p->left == x) p->left = c; else p->right = c; free(x); return root; } ``` Time: O(h), where h is the height of the tree. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. When deleting a BST node with exactly one child, what is done? A. The node is replaced by its inorder successor B. The child (with its subtree) replaces the node by linking to the node's parent C. Both subtrees are deleted D. The child's subtree is rebuilt Answer: B. The only child is attached directly to the deleted node's parent. (Key point: Deletion rule) 2. Why does the BST property remain valid? A. Keys are re-sorted afterwards B. Subtree keys are all changed C. The tree is rebalanced D. The child subtree already lies in the correct key range for that position Answer: D. All keys in the child subtree were already in the range allowed for the deleted node's position. (Key point: Why BST holds) 3. If X is the left child of its parent P, which update is made? A. P->right = C B. P->left = C C. X->left = P D. C->left = X Answer: B. C takes X's place on the same side of P. (Key point: Pointer update) 4. If the node to delete is the root with one child, what happens? A. The tree becomes empty B. The parent pointer is set to NULL C. The root is kept D. The child becomes the new root Answer: D. No parent exists, so the root pointer is set to C. Time complexity is O(h). (Key point: Deleting the root) ## Related in Data Structure and Algorithm - [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× - [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 - [Insert and delete before a node, singly linked](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Asingly-insert-delete-before) — Data Structure and Algorithm, chapter 4 - [Delete Kth node from doubly linked list](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Adoubly-delete-kth) — Data Structure and Algorithm, chapter 4 - [AVL delete then insert gives same tree?](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aavl-delete-insert-original) — Data Structure and Algorithm, chapter 6 ## Related in other subjects - [Boundary derivative with one-sided differences](https://www.bctengineer.com/question.md?key=semester_7%2Fapplied_computational_fluid_dynamics%3Aone-sided-boundary-derivative-numerical) — Applied Computational Fluid Dynamics, chapter 3 - [Linear shape functions for one-dimensional element](https://www.bctengineer.com/question.md?key=semester_8%2Ffinite_element_method%3Alinear-bar-shape-functions) — Finite Element Method, chapter 5 - [Variational approach for one-dimensional heat conduction](https://www.bctengineer.com/question.md?key=semester_8%2Ffinite_element_method%3Avariational-approach-heat-conduction) — Finite Element Method, chapter 5