Remove in Binary Search Tree
tags: create-link-with-return-value-from-recursion
In this article we will discuss how to implement remove operation in a binary search tree.
Remove Node
Consider the following binary search tree:
k
c t
a h m
f p
One way to remove c can result in the BST:
k
a t
h m
f p
The implementation discussed here results in the BST:
k
f t
a h m
p
|
|
Consider the case of removing the root node in the following binary search tree:
k
c t
a h m
f p
The inorder successor of the root must take the place of the root.
Consider the following binary search tree:
m
c t
a h _
f p
The child of inorder successor moves up to the vacant spot left by the inorder successor.
m
c t
a h p
f