What is a binary search tree? Write its properties. Suggest an example.

A Binary Search Tree (BST) is a tree data structure in which each node has at most two children, referred to as the left child and the right child. It is a type of binary tree but with the additional property that the key in each node must be greater than or equal to any key stored in the left sub-tree, and less than or equal to any key stored in the right sub-tree.

Properties of Binary Search Tree:

1. Ordered or Sorted Binary Tree: The left sub-tree of a node contains only nodes with keys less than the node’s key. The right sub-tree of a node contains only nodes with keys greater than the node’s key. Both the left and right sub-trees must also be a binary search tree.

2. Unique Entries: No two nodes in the tree can have the same key value.

3. Mutable: The structure of a BST can change with insertions and deletions, and it may become unbalanced.

4. Flexible Size: The number of nodes in a BST can dynamically increase or decrease as entries are added or removed.

5. Inorder Traversal of BST Retrieves Elements in Sorted Order: The inorder traversal of a binary search tree involves visiting each node in the tree in the order Left, Node, Right. When this traversal algorithm is applied to a BST, it visits the nodes in ascending order, i.e., the keys are sorted.

Here is an example of a binary search tree:

        8
       / \
      3   10
     / \    \
    1   6    14
       / \   /
      4   7 13

In this example, the root node is 8. For the root node:

• The left child is 3, and all nodes on the left of 8 are less than 8.
• The right child is 10, and all nodes on the right of 8 are greater than 8.

This property holds true for all nodes in the tree. For example, for the node with value 3:

• The left child is 1, which is less than 3.
• The right child is 6, which is greater than 3.

This is the property that differentiates a binary search tree from a regular binary tree.