How does binary tree recursive removeLeftmost() method work?

2
votes

The specification of the method claims that the method, starting from the root, will remove the leftmost node and repair the tree structure. It also says that if the leftmost node has no left child to attach a right child (may be null) to parent of leftmost node as left child (I don't see where this happens in the code). Here is the code:

public BTNode removeLeftmost()
{
    if (left == null)
        return right;

    left = left.removeLeftmost();
    return this;
}

I just don't see how it is returning back the whole tree with the leftmost node returned. Mainly the first part is confusing me where it says to return the right child if left == null. If I were deep into the tree (due to the recursive call), wouldn't returning right cut off a lot of the tree?

2
javatreebinary-treebinary-search-tree

2 Answers

1
votes

I'm assuming this is a binary search tree because otherwise you wouldn't need to repair the structure, correct?

So what it does is it moves along the tree until there are no more branches to the left, i.e. with respect only to the left, you have reached a leaf.

if (left !=null){ left = left.removeLeftmost(); }

At this point, it grafts the branch on the right of the child into that spot on the parent where the left tree was (by left = left.removeLeftmost(); again), and then it will return the branch that was previously in the same spot all the way back to the root of the tree.

1
votes

Here's the case it's handling:

          9
         / \ 
        8   12
       / \
      5   20
       \ 
        6
         \
          7

When we get to 5, it's the leftmost node (left == null). We need to remove it. So the right of 5 (i.e. 6) is returned to the caller (return right;), and the caller makes 6 the new left tree of 8 (left = left.removeLeftmost())..

          9
         / \
        8   12
       / \
      6   20
       \ 
        7

Then 8 is returned to the caller (return this) and assigned as the left node of 9 (left = left.removeLeftmost()). But 8 was already the left child of 9, so this doesn't change anything.