Binary Search Tree
Binary Search Tree (BST)
A Binary Search Tree (or BST) is a data structure used in computer science for organizing and storing data in a sorted manner. Each node in a Binary Search Tree has at most two children: a left child and a right child, with the left child containing values less than the parent node and the right child containing values greater than the parent node. This hierarchical structure allows for efficient searching, insertion, and deletion operations on the data stored in the tree.
Example
The tree below demonstrates a Binary Search Tree. Here, the root node is 40, all the nodes in the left subtree are smaller, and those in the right subtree are larger. This satisfies the BST property:
Properties of Binary Search Tree
- Each node has a value.
- The left subtree of a node contains only nodes with values less than the node's value.
- The right subtree of a node contains only nodes with values greater than the node's value.
- Both the left and right subtrees must also be binary search trees.
- There must be no duplicate nodes.