Binary Search Tree

Binary Search Trees (BST) are used as in-memory data structures in databases to store ordered data and for some types of abstract data, such as priority queues and lookup tables.

Terminology

Before diving in, let’s review a few important terms used for tree data structures:

• Root: The root is the topmost node in a tree with no parent.

• Leaves: Leaves are the bottommost nodes in the tree without children.

• Key: A unique identifier representing a node in the tree.

• Value: The data component associated with the key in the tree.

Overview

A BST is a sorted binary tree with the following properties:

• Only one root node.

• Every node has a key.

• Every node in the BST has at most two children.

• Every node splits the search space into left and right subtrees:

  • The left subtrees have node keys lesser than the parent node key.

  • The right subtrees have nodes greater than or equal to the parent node key.

Insertion

Insertion of a new key-value pair always happens at the leaf level after the following steps:

• The insertion starts by comparing the key with the tree's root.

• If the root node is empty, the new key-value pair becomes the root.

• The search branches towards the left subtree if the root key is greater than or equal to the search key for a nonempty tree.

• The search branches towards the right subtree if the root key is lesser than the search key.

• The search process repeats recursively until the leaf node.

• A new node is inserted to the left or right, depending on the key.

The illustration demonstrates the insertion of elements in a BST:

• Element 7 becomes the root node since the tree is empty.

• Since 4 < 7, insertion branches towards the left subtree and is inserted to the left of 7.

• Now, since 5 < 7 but 5 > 4, insertion branches the right subtree of 4 and is inserted to the right of 4.

• Since 3 < 7 and 3 ...