CODEWITHSUNDEEP
data-structurestreebinary-treebinary-search-tree
Jimmy Gong
Jimmy Gong

Reputation: 1955

Binary Search Tree deletion procedure with children

Wasn't sure how to word this question. Basically take the following BST:

       25
     /    \
   20      30
  /  \      / \
 18   23  27   31
/  \   /\
8  19 22 24

If I were to delete the value 25 and rotate the value 20 in its place, does it make more sense to append the 23 subtree to 27, or to append the 30 subtree to 24. And I don't mean specific to this case, but from a broader perspective.

Just to be clear, what is preferable between these two arrangements:

      20
    /    \
  18      23
 /  \      / \
8   19    22  24
                \
                 30
                /  \
              27   31

      20
    /    \
  18      30
 /  \     / \
8   19  27  31
        /
       23
      /  \
     22  24

Upvotes: 1

Views: 28

Answers (1)

chickenman
chickenman

Reputation: 798

rotating 20 would not be the wisest decision. You should either replace it with the maximum value of the left sub-tree or the minimum value of the right sub-tree.

If you do wish to rotate the way you have, there is no difference between the heights of the tree's and both will be same in terms of time complexity.

Upvotes: 1

Related Questions