Binary Search Tree

A Binary Search Tree (BST) is a tree in which all of the nodes have the following properties:

The key of the left sub-tree has a lower value than the key of its parent (root) node.

The key of the right sub-tree is greater than or equal to the key of its parent (root) node.

As a result, BST separates all of its subtrees into two segments: the left subtree and the right subtree, and may be characterized as :

left_subtree (keys) < node (key) ≤ right_subtree (keys)

BST is a set of nodes that are structured in such a way that they retain BST attributes. Each node has a key and a value associated with it. The required key is compared to the keys in BST when searching, and if found, the related value is obtained.

Following is a pictorial representation of BST −

Basic Operations

Following are the basic operations of a tree −

• Search − Searches an element in a tree.
• Insert − Inserts an element in a tree.
• Pre-order Traversal − Traverses a tree in a pre-order manner.
• In-order Traversal − Traverses a tree in an in-order manner.
• Post-order Traversal − Traverses a tree in a post-order manner.

Node

Define a node having some data, and references to its left and right child nodes.

Search Operation

When looking for an element, begin your search at the root node. If the data is less than the key value, look for it in the left subtree. Otherwise, look for a said element in the appropriate subtree. For each node, use the same algorithm.

Insert Operation

When inserting an element, first determine its suitable placement. Begin your search at the root node, and if the data is less than the unique key, go to the left subtree and enter the data. Otherwise, find an empty position in the appropriate subtree and insert the data.