CODEWITHSUNDEEP
algorithmdata-structuresbinary-search-tree
Daniel Thompson
Daniel Thompson

Reputation: 2351

Why would two nodes of a BST be in the wrong place, anyway?

"Two nodes swapped, correct the BST" seems to be a very discussed/popular algorithm.

What is so special about this 'swap two faulty BST nodes' algorithm as opposed to some other more general BST repair algorithm?

Upvotes: 1

Views: 68

Answers (1)

templatetypedef
templatetypedef

Reputation: 373012

I could be wrong, but I suspect this problem is 100% contrived and is simply a good exercise to assess whether you have a handle on binary search trees, inorder traversals, and general tree recursion. It strikes me as exceedingly unlikely that you'd ever use this in practice, since getting the elements of a BST out of order usually indicates a bug or logic error somewhere.

The second question you asked - what about a more general "fix this tree to make it a binary search tree" problem? - is a good one. That's essentially equivalent to sorting the elements of a binary tree and then using an inorder traversal to put the elements into the right place (do you see why?) Again, I'd be very surprised if you ever actually ended up doing anything like this, since it's unusual to store unordered elements in a binary tree and then decide to reorder them this way.

Upvotes: 1

Related Questions