Binary Search Tree Node Removal: How to decide which subtree to traverse for removal? (If node has two children)

1
votes

I am seeking help in understanding Binary search tree removals when a node has two children.

What I know is that when a BST node to be removed has two children, one can find either the smallest value starting from the right subtree or the largest value from the left subtree.

Which subtree should I traverse by default- should I use the right or left subtree ? Under what conditions should I pick the left/right subtree? How much does this choice matter?

Please bear with me, as I'm a newbie to DS and algos.

1
data-structuresbinary-search-tree

1 Answers

1
votes

If the tree is more or less balanced, it won’t matter which subtree you traverse to find the replacement.

Otherwise, if the tree is left heavy then going to right sub-tree and picking the smallest value could be quicker. Vice-versa if the tree is right heavy.

Also, whether the BST has only unique values or whether the tree has duplicates, picking the root replacement from left subtree or right subtree will not affect the tree invariant.