Alg.21 BST Construction

From algoexpert.io

Definition of a valid Binary Search Tree: its value is strictly greater than its left node; its value is less than or equal to its right node; its children nodes are either valid BST node or null.

Write a BST class for a Binary Search Tree. The class supports 3 functions:

1. insert: insert a node with given value;
2. remove: remove a node, only remove first instance of a given value;
3. contains: search with a given value.

Here are the structure of the code implementations:

class Program {
  static class BST {
  
    public int value;
    public BST left;
    public BST right;

    public BST(int value) {
      this.value = value;
    }

    public BST insert(int value) {
      
    }

    public boolean contains(int value) {
      
    }

    public BST remove(int value) {
      // Do not edit the return statement of this method.
      remove(value, null);
      return this;
    }
  }
}

For insert function: we can either use recursion way or iteration way to find the expecting location of the given node. For the most cases, the BST will be assumed as balanced, but when the tree is skewed, we have the worst case, and the insert process will be completed within O(n). If we use recursion here, the average space complexity will also be O(logn) since we have to use the call stacks, the worst space complexity is O(n), too.

public BST insert(int value) {
    BST current = this;
    while (true) {
        if (value >= current.value) {
            if (current.right == null) {
                current.right = new BST(value);
                break;
            } else {
                current = current.right;
            }
        } else {
            if (current.left == null) {
                current.left = new BST(value);
                break;
            } else {
                current = current.left;
            }
        }
    }
  return this;  
}

Time complexity: average: O(logn), worst: O(n);

Space complexity: O(1).

For the contains function, it is much simpler than the insert function. Also, the time&space analysis of the recursion version is the same as insert function.

public boolean contains(int value) {
    BST current = this;
    while (current != null) {
        if (current.value > value) {
            current = current.left;
        } else if (current.value < value) {
                current = current.right;
        } else return true;
    }
  return false;
}

Time complexity: average: O(logn), worst: O(n);

Space complexity: O(1).

remove function is much more difficult than the other 2 to implement, there are so many edge cases to consider, let’s dig into the code implementation.



Here is the iteration version, first of all, we need to keep track on the parent node of the current node. From the figure above, when we find the node that we want to delete, there are several conditions:

1. The node has left and right children nodes, whether it is a root node, we can make its right branch’s smallest node replace it;
2. The node has 1 or 0 children node and it is a root node, when it has only 1 children node, we use its children node to replace it; when it has no children node, we just leave it there and do nothing;
3. The node has 1 or 0 children node and it is not a root node, we just use its children node or null to replace its place.

       
   public void remove(int value, BST parent) {
       BST current = this;
       while (current != null) {
           if (current.value > value) {
               parent = current;
               current = current.left;
           } else if (current.value < value) {
               parent = current;
               current = current.right;
           } else {
               if (current.left != null && current.right != null) {
                   current.value = current.right.getMinValue();
                   current.right.remove(current.value, current);
               } else if (parent == null) {
                   if (current.left != null) {
                       // The order here is very important, since we can't update
                       // the left branch first
                       current.value = current.left.value;
                       current.right = current.left.right;
                       current.left = current.left.left;
                   } else if (current.right != null) {
                       current.value = current.right.value;
                       current.left = current.right.left;
                       current.right = current.right.right;
                   } else {
                   
               }
           } else if(parent.left == current) {
               if (current.left != null) parent.left = current.left;
               else parent.left = current.right;
           } else if(parent.right == current) {
               if (current.left != null) parent.right = current.left;
               else parent.right = current.right;
           }
           break;
           }
       }
   }
       
   private int getMinValue() {
       BST current = this;
       while (current.left != null) {
           current = current.left;
       }
       return current.value;
   }

   Time complexity: average: O(logn), worst: O(n);
   
   Space complexity: O(1).
   

Donate