What is a Binary Search Tree (BST)?

This lesson will introduce Binary Search Trees and their properties.

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)(username,bank) or (employee,employeeID)(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.