What is a Binary Search Tree (BST)?

This lesson will introduce Binary Search Trees and their properties.

We'll cover the following

Introduction
- The BST Rule
- Examples
Binary Search Trees vs. Binary Trees
- 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)$ .

The BST Rule

For all the nodes in a BST, the values of all the nodes in the left subtree of a node are less than the value of that node. All the values in the right subtree of a node are greater than the value of that node. This is referred to as the BST rule.

NodeValues(left subtree of Node n) $<$ Node Value of Node n $<$ NodeValues(right subtree of Node n)

Examples

Let’s see a few examples of BSTs:

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

Introduction to Complexity Measures

Introduction to Arrays

Introduction to Linked Lists

Introduction to Stack/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

The BST Rule

Examples