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). 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(leftsubtree)<=CurrentNodeValue<NodeValues(rightsubtree)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.