A Binary Search Tree or BTS in the data structure is a tree of elements. In Binary Seach Tree, each node follow the following properties-
The value of all the keys of the left subtree is smaller than the value of the keys of its parent node.
The value of the key of the right subtree is greater than or equal to the value of the key of its parent node.
Thus in a binary search tree, all its sub-trees are divided into two segments, the right subtree, and the left subtree, and defined as-
left_subtree (keys) < node (key) ≤ right_subtree (keys)
How binary search trees are represented:
A binary Search tree is an arrangement of nodes in a systematic manner where all the properties of Binary Search trees are maintained. Each node has a key and an associated value While searching the desired element it is compared to all the keys in Binary Search Tree. The associated value of the key is retrieved if the desired key is found.
Following is a pictorial representation of BST −
All the keys of the left subtree have values less than the root node key (27) and all the keys on all the right subtrees have higher than the root node key. Also, the parent node keys (10,14,19) have higher values than the keys of the left subtrees and smaller values 31,35,42) than the right subtrees.
Basic operations in Binary Search Tree:
Following are the basic operations performed in Binary Search 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
Whenever you have to search an element from a Binary search tree, start searching from the root node.
If the data is greater than the value of the key value of the root node, start searching on the right subtree and escape the left subtree. If the data is smaller than the key value of the root node, start searching to the left subtree. Repeat the same process until you find our data.
Whenever you have to insert any element in the Binary search tree, locate its proper location in the tree first. Follow the same steps of the search operation. Start searching from the root node. If the data is less than the key value of the root node, search for the empty location in the left subtree and insert the element. If data is greater than the key value of root node, start searching in the right subtree and insert the data.
To know more about the binary search tree and binary search tree examples visit https://www.helpmestudybro.com/