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.

How to Build Binary Search Tree.

Let's start by defining tree Node.

Java

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

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

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

\text{arr} = \begin{bmatrix} \text{30, 20, 10, 40, 50, 25, 35} \end{bmatrix}

Java

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

  if(key < root.key) 
    root.left = insert(root.left, key);
  else if(key > root.key) 
    root.right = insert(root.right, key);

  return root;
}

Binary Search tree will look like below:

How to Use Binary Search Tree

Let's start by searching a key in binary search tree.

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 rootl
}

How to 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 begin by defining the delete operation.

Java

public TreeNode inorderPredecessor(TreeNode root) {
  while(root.left != null) {
    root = root.left;
  }
  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.right);
      root.key = inorderPredecessor.key;
      root.right = delete(root.right, inorderPredecessor.key);
      return root;
    }
  }
}

Now, update operation will look like below:

Java

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