Binary Search Tree

Introduction

A binary search tree (BST) is a fundamental data structure in computer science used for efficient searching, insertion, and deletion of elements.

Properties

• Each node has at most two children: left and right
• The value of nodes in the left subtree is less than the value of the parent node, and the value of nodes in the right subtree is greater than the value of the parent node
• Allows for efficient search, insert, and delete operations with average time complexity of O(log n)

Algorithm

1. Start at the root node
2. If the target value is equal to the current node's value, return the node
3. If the target value is less than the current node's value, move to the left child
4. If the target value is greater than the current node's value, move to the right child
5. Repeat steps 2-4 until the target value is found or until reaching a leaf node

Implementation

Below is an image depicting a binary search tree:

Learn More

For more information about binary search trees, visit the Wikipedia page.