Binary Search Tree
- BST is a non-linear data structure.
- One data element is connected to multiple elements in this structure.
- We represent the data in nodes.
- Every node has 3 fields
- Data filed
- Left child
- Right child
- In BST, every node has at most 2 children.
The tree with N nodes having N+1 null nodes.
Tree memory representation with NULL nodes:
The following example shows how the elements will be inserted into BST:
Node structure: We represent the node using user data type called structure.
struct Node *left;
struct Node *right;
struct Node *root=NULL;
Operations on BST:
- Inserting node in BST
- Delete node from BST
- Traverse BST
Note the followings:
- We can store duplicate values into BST but it is not recommended.
- Nodes are working like keys to store the information.
- Keys always unique in the process of storing information.