Binary Search Tree

A binary search tree (BST) is a type of ordered binary tree that is used to maintain a dynamic set of numbers or other comparable elements. The defining characteristic of a BST is that for each node, all elements in the left subtree have values less than the node’s value, and all elements in the right subtree have values greater than the node’s value. This property must hold true for all nodes in the tree, ensuring that the tree is ordered. Importantly, binary search trees do not allow duplicate values.

Structure and Properties

In a binary search tree, each node contains a value and two branches, often referred to as the left and right children. The left branch of a node contains values that are less than the node’s value, while the right branch contains values that are greater. This structure allows for efficient searching, insertion, and deletion operations, as the tree can be traversed in a manner similar to binary search.

One of the key features of a binary search tree is its immutability and persistence. This means that operations such as insertions do not modify the existing tree. Instead, they create a new tree that reflects the changes. This property is particularly useful in functional programming, where immutability is a common paradigm.

Example

To better understand the structure of a binary search tree, consider the following example:

Figure 10.4. An example of an ordered tree, or binary search tree (BST)

In this figure, you can see a visual representation of a binary search tree. Each node is connected to two branches, with the left branch containing values less than the node’s value and the right branch containing values greater than the node’s value. This structure allows for efficient operations and maintains the ordered property of the tree.