Binary Search Tree
Learn the fundamentals of binary search trees and their insertion and search mechanics.
We'll cover the following
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.
Get hands-on with 1200+ tech skills courses.