DS – Binary Search Tree

Binary Search Tree

Introduction:

• 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 {             int data;             struct Node *left;             struct Node *right;      }; struct Node *root=NULL;

Operations on BST:

1. Inserting node in BST
2. Delete node from BST
3. 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.