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.