Binary Search Tree

This page provides introduction to Binary Search Tree.

Overview

A Binary Search Tree (BST) is a special kind of binary tree that's useful for searching and sorting in $\text{O(n * log n)}$ time. It has the following properties

All nodes in its left subtree have values less than the node's value.
All nodes in its right subtree have values greater than the node's value.

Binary search trees come in various forms, including balanced and unbalanced ones. Balanced BSTs, such as AVL trees and Red-Black trees, maintain a balanced structure to ensure that the tree height remains logarithmic, guaranteeing efficient operations even in worst-case scenarios.

Build Binary Search Tree.

Let's build a Binary Search tree for the array below:

\text{arr} = [30, 20, 10, 40, 50, 25, 35]

We will begin by defining tree Node.

Java

class TreeNode {
  int key;
  TreeNode left;
  TreeNode right;

  public TreeNode(int key) {
    this.key = key;
  }
}

If the root node of the current BST is null, create a single node and return it as the root of the tree.

Next, we will add $20$ , which is less than the root node, so it goes to the left subtree of the root node.

Similarly, adding $10$ to BST.

Adding $40$ to BST.

Adding $50$ to BST.

Adding $25$ to BST.

Adding $35$ to BST.

Java

TreeNode root;

public void insert(int key) {
  if(this.root == null) this.root = new TreeNode(key);
  else helper(this.root, key);
}

public TreeNode helper(TreeNode current, int key) {
  if(current == null) return new TreeNode(key);

  if(key < current.key) 
    current.left = helper(current.left, key);
  else if(key > current.key) 
    current.right = helper(current.right, key);

  return current;
}

Use Binary Search Tree

Let's search for key $35$ in binary search tree.

\text{arr} = [30, 20, 10, 40, 50, 25, 35]

We will start searching from the root node of the binary search tree. Since the root node's key is less than $35$ , we will continue the search in the right subtree.

Next, the key of the current node, $40$ , is greater than $35$ , so we will proceed with the search in the left subtree.

Finally, we find the key at the current tree node and return the tree node instance.

Java

public TreeNode search(TreeNode root, int key) {
  if(root == null) return root;

  if(key < root.key) {
    return search(root.left, key);
  }
  else if(key > root.key) {
    return search(root.right, key);
  }
  return root;
}

Update Binary Tree

To update a node in a binary search tree, we first delete the existing node and then add a new node to the tree.

Let's start by learning delete operation first. When deleting a node from a binary search tree, there are four main conditions to consider:

Leaf Node: If the node to be deleted has no children, simply remove it from the binary search tree.
Only Right Subtree: If the node to be deleted has only a right subtree, delete the node and attach the right subtree to its parent.
Only Left Subtree: If the node to be deleted has only a left subtree, delete the node and attach the left subtree to its parent.
Both Subtrees: If the node to be deleted has both subtrees, find the inorder predecessor(or successor) of the node, replace the key of the node to be deleted with the inorder predecessor's key, and then delete the inorder predecessor node.

info

Instead of replacing the key of the node to be deleted with the inorder predecessor, we could have also replaced it with the inorder successor, and the result would still be a binary search tree. The inorder successor is the leftmost leaf node in the right subtree of the node to be deleted.

Let's delete the root node $30$ from the binary search tree below.

Since the node to be deleted has both a right and a left subtree, it falls under the fourth category. We start by finding the inorder predecessor of the node to be deleted, which is the node that would come immediately before it during an inorder traversal of the binary search tree. To find the inorder predecessor of any node, move to its left child and continue traversing to the right until you reach a leaf node.

Replace the key of the node to be deleted with the inorder predecessor's key, $25$ .

Delete the inorder predecessor's key, $25$ , from the left subtree of the node to be deleted. This deletion falls under the first category, where we simply remove the node since it has no children.

info

Note that after deleting the root node $30$ , the binary tree still maintains all the properties of a binary search tree.

Java

public TreeNode inorderPredecessor(TreeNode root) {
  while(root.right != null) root = root.right;
  return root;
}

public TreeNode delete(TreeNode root, int key) {
  if(root == null) return root;

  if(key < root.key) {
    root.left = delete(root.left, key);
  }
  else if(key > root.key) {
    root.right = delete(root.right, key);
  }
  else {
    if(root.left == null) return root.right;
    else if(root.right == null) return root.left;
    else {
      TreeNode inorderPredecessor = inorderPredecessor(root.left);
      root.key = inorderPredecessor.key;
      // delete inorder predecessor
      root.left = delete(root.left, inorderPredecessor.key);
      return root;
    }
  }
}

Once a key is deleted, we can simply add a new key to the binary search tree to complete the update operation.

Java

public TreeNode update(TreeNode root, int oldKey, int newKey) {
  delete(root, oldKey);
  insert(root, newKey);
  return root;
}