Spread the post

Delete Binary search tree (BST) node

Three possible position to delete binary search tree nodes.

1) Delete leaf node

2) Delete internal node

3) Delete root node

Suppose BST contain following nodes.


Try it Yourself

Visualize memory allocation and pointer position

Stack Areamainroot(pointer) Heap Areastruct Treedata (int)= 20left_child (pointer) right_child (pointer) struct Treedata (int)= 10left_child (pointer) right_child (pointer) struct Treedata (int)= 30left_child (pointer) right_child (pointer) struct Treedata (int)= 25left_child (pointer)= NULLright_child (pointer)= NULLstruct Treedata (int)= 40left_child (pointer) right_child (pointer)= NULLstruct Treedata (int)= 35left_child (pointer)= NULLright_child (pointer)= NULLstruct Treedata (int)= 3left_child (pointer)= NULLright_child (pointer) struct Treedata (int)= 15left_child (pointer) right_child (pointer)= NULLstruct Treedata (int)= 5left_child (pointer)= NULLright_child (pointer)= NULLstruct Treedata (int)= 11left_child (pointer)= NULLright_child (pointer)= NULL

Try it Yourself

Delete leaf node

Delete Leaf node[5].

2010302540353155Delete Leaf node 511

After Delete Leaf node [5].


Internal nodes leaf node

Delete node [30].

201030Delete Internal Node 3025403531511

Relace 30 to 25 and delete 25.


3) When delete node 20

Same process to delete internal node.

201025403531511Delete Root [20]

After delete root node.


C program to delete Binary search tree nodes.


Code execution process.

Spread the post

Recommended Posts: