CODEWITHSUNDEEP
data-structuresbinary-search-tree
user14401314
user14401314

Reputation: 41

Can we replace the deleted node by its direct child nodes (instead of replacing by its inorder predecessor or successor) in Binary Search Tree?

As we know that to delete any node in BST we replace that deleted node with its inorder predecessor or successor.
I've tried a new approach in which I replace the deleted node either by its direct left child or by its direct right child (instead of replacing by its inorder pred. or succ.). And I think that this approach is valid for every node in BST. Program for this approach will be also easy as less number of links are changed for a node.I am attaching 2 pics to make you understand my approach.
Is my approach of deleting a node in BST is right or wrong? If wrong then why?

Example 1

Example 2

Upvotes: 3

Views: 3248

Answers (2)

Daniel Akwueze
Daniel Akwueze

Reputation: 46

While this is a valid way to delete a node in a binary tree, it won't always work for binary search trees. Let's say you want to delete 40 and 35 has a right child, by connecting 35 to 45, you'll be losing its original right child and every other node connected to it (you'll be losing a subtree). For binary search trees (BST), its better to replace the node with the rightmost node of the left subtree, which in this case is still 35 (this guarantees it does not have a right child) or the leftmost node of the right subtree if there is no left subtree.

Upvotes: 0

backward forward
backward forward

Reputation: 467

This can get pretty complicated, but you'll probably want to look into some rotations.

Say you have a full tree with 5 levels, and you are trying to delete the roots right child, which contains a quite a few more nodes. The issue is that by simply replacing with it's left or right child, would result in the deleted index "having" more than two child, which as I'm sure you know, is an invalid BST.

The solution? Rotations!

Here are a couple links that explain with some pictures.

http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/BST-delete2.html

Upvotes: 0

Related Questions