What is a Binary Search Tree (BST)?

This lesson will introduce Binary Search Trees and their properties

We'll cover the following

Introduction
- Examples
Binary Search Trees vs. Binary Tree
- Explanation

Introduction

Binary Search Trees (BSTs) are a special kind of binary tree where each node of the tree has key-value pairs. These key-value pairs can be anything, like $(username,bank)$ or $(employee, employeeID)$ . For all the nodes in a BST, the values of all the keys in the left sub-tree of the node are less than the value of the nodes themselves. All the keys in the right subtree are greater than the values of the node. This is referred to as the BST rule.

$NodeValues(left subtree)<=CurrentNodeValue<NodeValues(right subtree)$

Examples

Let’s see a few examples of BSTs

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.

Introduction to Complexity Measures

Introduction to Lists

Introduction to Linked Lists

Introduction to Stacks and Queues

Introduction to Graphs

Introduction to Trees

Trie

Introduction to Heap

Introduction to Hashing

Summary of Data Structures

What is a Binary Search Tree (BST)?

Introduction

Examples