Binary Search Tree

Binary Search Tree is a Binary Tree in which all the nodes follow these properties:

• Left sub-tree of a node has a value <= its parent node’s value
• Right sub-tree of a node has a value >= its parent node’s value

               8
             /    \
          /         \
        3           10
      /     \         \
    1        6        14
            / \      /
          4    7    13

Why Binary Search Tree

So we have Binary Tree, why do we need Binary Search Tree?

Let’s first take a look at the time complexity between both Trees:

By using the properties of a Binary Search Tree, we can then improve most of the operations from O(n) to O(log n).

Searching for a node

We’ll start from the root of the tree. If the value is greater than the root node’s value, we search in the right sub-tree and if it is smaller, we search for it in the left sub-tree.

# Search value = 90

             *100
            /     \
          /         \
        *80         200
      /     \      /   \
     70    *90*   150  300
    /                 /   \
   50               250   400
 /    \
40    60

# It will go from 100 -> 80 -> 90.

Here’s how the code will look like.

type Node = {
  value: number;
  left: Node;
  right: Node;
};

function bstSearchNode(root: Node, value: number): Node {
  if (!root) throw new Error();

  if (value === root.value) {
    return root;
  } else if (value < root.value) {
    return bstSearchNode(root.left, value);
  } else {
    return bstSearchNode(root.right, value);
  }
}

Traversing through a Binary Search Tree

There are 4 ways to traverse through a Binary Tree.

• Depth First Search

  • Pre-order
  • In-order
  • Post-order

• Breadth First Search

  • Level-order

  Check out the posts above to understand more.

  Using In-order traversal on the Binary Search Tree means that the traversal is progressed in a sorted manner.

Inserting a node

Depending on the value of the node, we either go left or right.

# New value = 85

             *100
            /     \
          /         \
        *80         200
      /     \      /   \
     70    *90    150  300
    /      /          /   \
   50    *85*       250   400
 /    \
40    60

# New value = 140

             *100
            /     \
          /         \
         80        *200
      /     \      /   \
     70     90   *150  300
    /           /     /   \
   50        *140*   250  400
 /    \
40    60

And here’s how the code will look like.

type Node = {
  value: number;
  left: Node;
  right: Node;
};

function bstInsertNode(node: Node, value: number) {
  if (!node) {
    node = new Node(value);
  } else if (value < node.value) {
    node.left = bstInsertNode(node.left, value);
  } else {
    node.right = bstInsertNode(node.right, value);
  }
  return node;
}

Deleting a node

There are 3 cases to take note when deleting a node:

• Node is a leaf node
• Node has 1 child
• Node has 2 children

# Case 1 - Node is a leaf node, value = 60

             *100
            /     \
          /         \
        *80         200
      /     \      /   \
    *70     90    150  300
    /                 /   \
  *50                250  400
 /    \
40   *60*

# Since there are no children dependent we can safely delete it

# Case 2 - Node has 1 child, value = 80

 ----------- *100
 |          /     \
 |        /         \
 |      *80*         200
 |     /             /   \
 |-- 70            150  300
    /                  /   \
   50                250  400
 /    \
40    60

              100
            /     \
          /         \
        70          200
       /           /   \
     50          150  300
    /  \             /   \
   40  60          250  400

# In a case like this, we find Node 80's parent and link it to Node 80's child

# Case 3 - Node has 2 children, value = 100

             *100*
            /     \
          /         \
         80         200
      /     \      /   \
     70     90    150  300
    /            /    /   \
   50         *140   250  400
 /    \
40    60

              140
            /     \
          /         \
         80         200
      /     \      /   \
     70     90    150  300
    /                 /   \
   50                250  400
 /    \
40    60

# Case 3 - Node has 2 children, value = 100

             *100*
            /     \
          /         \
         80          200
      /     \      /     \
     70     90   *150    300
    /               \   /   \
   50              160 250  400
 /    \           /   \
40    60        155  170

              150
            /     \
          /         \
         80         200
      /     \      /    \
     70     90   160    300
    /           /   \   /   \
   50          155 170 250  400
 /    \
40    60

# In a case like this, since the successor 150 has dependents, we then need to see which case scenario it belongs and process it.

The algorithm is more complex and here’s how the code will look like.

type Node = {
  value: number;
  left: Node;
  right: Node;
};

function minNode(node: Node) {
  if (!node.left) return node;
  return minNode(node.left);
}

function bstDeleteNode(node: Node, value) {
  if (!node) throw new Error();
  if (value < node.value) {
    node.left = bstDeleteNode(node.left, value);
  } else if (value > node.value) {
    node.right = bstDeleteNode(node.right, value);
  } else {                                                          // this is the node to be deleted
    if (node.left && node.right) {                                    // case 3
      const minRightNode = minNode(node.right);                         // find min value node from right subtree
      node.value = minRightNode.value;                                  // replace current node value with min value from right subtree
      node.right = bstDeleteNode(node.right, minRightNode.value);       // delete min node from right subtree
    } else if(node.left && !node.right) {                             // case 2
      node = node.left;
    } else if(node.right && !node.left) {                             // case 2
      node = node.right;
    } else {                                                          // case 1
      node = null;
    }
  }
  return node;
}

Depending on the incoming data into a Binary Search Tree, it can get skewed and its performance starts decreasing. Instead of O(log n), it can go up to O(n). Hence, AVL Tree to the rescue!