Binary Search Tree (BST)

Introduction

A Binary Search Tree is a node-based binary tree data structure which has the following properties:

• The left subtree of a node contains only nodes with keys lesser than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• The left and right subtree each must also be a binary search tree.
• There are no duplicate nodes.

Operations

Insertion

To insert a new node, start from the root and compare it with the key:

1. If the new key is less, go to the left child.
2. If the new key is more, go to the right child.
3. Repeat until the correct leaf node is found for insertion.

Deletion

Deletion in a BST can be more complex and requires three cases to consider:

1. Deleting a leaf (node with no children).
2. Deleting a node with one child.
3. Deleting a node with two children.

Learn More

For more information on Binary Search Trees, visit Wikipedia.