CODEWITHSUNDEEP
algorithmbinary-tree
Nikita
Nikita

Reputation: 325

Binary tree deletion

I have a binary tree, and pre-order traversal. Here is my tree. 

      15
     / \
   10   23
   /\   /\
  5 12 20 30
    /     /
   11    25
          \
          27

so result of pre-order : 15 10 5 12 11 23 20 30 25 27. It's OK

Than I delete 5,12 and 23 elements

Should I get this

          15
         / \
       10   27
        \   /\
        11 20 30
               \
               25

Result:15 10 11 27 20 30 25

or this?

      15
     / \
   10   25
    \   /\
    11 20 30
          /
         27

Result: 15 10 11 25 20 30 27

P.S I get 2nd case. If it isn't right, what is wrong with deletion?

UPD: SO the second updated variant is right?

Upvotes: 2

Views: 774

Answers (2)

Manny D
Manny D

Reputation: 20714

Your 2nd case is almost right. 27 would be a left node of 30. When deleting a top node of a (sub)tree, you can either replace that node with the right-most node of the left branch or the left-most node of the right branch. In this case, you've replaced 30 with the left-most value of the right branch, which is 25. You'd have to perform this recursively as 25 has branches of its own. Once your target node to delete becomes a leaf, delete it.

First step:

      15
     / \
   10   25
    \   /\
    11 20 30
          /
         23
          \
           27

Second step:

      15
     / \
   10   25
    \   /\
    11 20 30
          /
         27
        / 
       23

Third (deletion):

      15
     / \
   10   25
    \   /\
    11 20 30
          /
         27

Upvotes: 1

Ted Hopp
Ted Hopp

Reputation: 234795

If you want pre-order traversal of the remaining elements to be consistent with the pre-order traversal before the deletes, then your tree should look like this:

   15
  / \
10   20
 \    \
 11    30
       /
      25
       \
        27

The delete method is:

If there's a left subtree of a deleted node, move the root of the left subtree to the deleted position. Follow the right subtree links in the (formerly) left subtree and attach the right subtree to the first empty right link. If there is no left subtree, move the root of the right subtree to the deleted position.

Upvotes: 0

Related Questions