DEV Community

Discussion on: Binary Trees (Part 3) - Deleting Nodes in Binary-Search Trees

View post
Collapse
 
luismartinez profile image
Luis Martinez • • Edited

Hi Jenny,

Excellent and very useful explanation.

I think there is a typo in the loop:

        while(!temp.left) {
        temp = temp.left;
      }
Enter fullscreen mode Exit fullscreen mode

I think it should be "while(temp.left) ..." (without the bang symbol) to check that there is still a left child.

I tested the code for the below binary tree:

let tree = new BinarySearchTree();
tree.insert(10)
tree.insert(5)
tree.insert(13)
tree.insert(11)
tree.insert(2)
tree.insert(16)
tree.insert(7)

which yields the below tree:

         Binary Tree
             10
      5              13
  2       7      11      16
Enter fullscreen mode Exit fullscreen mode

When trying to use the method to remove 13, I expected the minimum successor of 13, that is, 16, to replace 13 and get the below tree:

       Binary Tree
            10
      5              16
  2       7      11
Enter fullscreen mode Exit fullscreen mode

with a resulting depth-first-search inOrder(DFSInOrder) array of:
[2,5,7,10,11,16]

However, the actual result I get from calling the function is:

       Binary Tree
             10
      5              
  2       7
Enter fullscreen mode Exit fullscreen mode

with a DFSInOrder array of [2,5,7,10]; that is, the function removes the 13 node with all of its children (instead of replacing its value with its minimum successor and deleting the minimum successor). I'll try to come back to this problem if I find a solution that returns the expected DFSInOrder array of [2,5,7,10,11,16].