Binary Search Tree in Tree Data Structure || what is Binary Search Tree
Binary Search Tree :-
A Binary Search Tree 'T' is a binary tree either it is empty or each node in the tree contains an identifier and :-
1. an identifier in the left subtree are less numerically or alphabetically that the identifier in the root node.
2. All identify in the right subtree are greater than or equal to the identifier in the root node.
3. The left and right subtree are also act as a binary search tree.
In other words we can say that a binary tree is said to be BST if it is satisfy the following property.
Value at
LST < Value at Root Node <= Value at RST
Representation
BST is a collection of no. of nodes arranged in a Hierarchical way where its maintain the Binary Search Tree property. Every node has a key and an associat value. While searching is the desired key is compared to the keys in Binary Search Tree and if found, the associat value is retrieved.
Fundamental Operation :-
Following are the Fundamental operations of the tree −
Search − Searching is an element in a tree.
Insert − Inserting is an element in a tree.
Pre-order Traversal − Traversing is a tree in a pre-order manner.
In-order Traversal − Traversing is a tree in an in-order manner.
Post-order Traversal − Traversing a tree in a post-order manner.
A appropriate BST is defined as follows:
- The left sub tree of the node contains only one nodes with keys less than the node's key.
- The right sub tree of the node contains only nodes with keys greater than the node's key.
- Both the left and right sub trees must also be binary search trees.