CODEWITHSUNDEEP
algorithmbinary-treebinary-search-tree
user129506
user129506

Reputation: 337

Ways to delete a node in a binary tree

I'm following a book which explains how to delete nodes from a binary search tree, basically if we have this tree:

       10
      /  \
     4    100
    / \
   1   8
      / \
     6   9
      \
       7

and we want to delete node 4, the book says I should:

  1. Find 4's successor in its right subtree (which is 6)
  2. Exchange 4 and 6
  3. Delete 6 from the right subtree
  4. Attach the left subtree of 4 (which is just 1 in this case) to the new node 6

thus we get

       10
      /  \
     6    100
    / \
   1   8
      / \
     7   9

However I thought of another way to do this:

  1. Find 4 right subtree's minimum element (which is 6)
  2. Attach 4's left subtree to 6 (it won't have a left child)
  3. Attach the parent (10) to 4's right element (8). If the algorithm is recursive we can just return 8

thus we get

       10
      /  \
     8    100
    / \
   6   9
  / \
 1   7

Now I'd like to ask: I see that my solution produces (at least in this case) a slightly more unbalanced tree.

Is there a reason why I should use my book's one instead of my own? It seems my solution is easier (at least from my point of view) to implement but I'd prefer someone else to point out if I'm mistaken.

Upvotes: 0

Views: 1386

Answers (2)

Bernhard Barker
Bernhard Barker

Reputation: 55609

The code for neither approach is particularly complex.

Your approach generally will produce a less balanced tree, as you're taking a subtree (1's subtree) and moving it (possibly) very far down the tree.

With their approach, 7's subtree moves up 1 node and no other subtrees move.

It may simply be that they hadn't considered your approach, or, if they had, they likely would've picked theirs, because the less balanced the tree is, the worse the performance of queries on it.

Although this discussion isn't particularly significant, as basic binary search trees are rarely used in practice - self-balancing ones are used instead (to which one can make a much stronger argument because of trying to maintain certain properties to keep the tree balanced).

Upvotes: 2

L. Young
L. Young

Reputation: 173

When your tree is unbalanced the time to traverse the tree increases and thus you lose some benefits of using a BST.

Upvotes: 0

Related Questions