Binary Search TreeBinary Search Tree is one of most applicable principle using binary trees. Binary Search Tree is a special case of binary tree. It is used to store elements in the sorted order. Binary search tree are often used in the backend of many applications like database server and other data record management applications.
Data StructureBinary Search Tree also uses same data structure as it is used for simple binary tree. There is a member to hold the value in the structure and two pointers called left and right to hold the reference for left and right sub nodes.
Adding a nodeAllocation of a new node is done with the same logic as normal binary tree node allocation. Now a new record is allocated it should be compared with the parent node and placed in the left sub tree if its value is less than parent else that is placed in the right sub tree. This addition is recursive in nature and comparison goes from root to lower sub tree level till the condition is reached.
Printing/Traversing TreeTraversal of binary search tree is done with in-order fashion. Every node has a value greater than its left node and less than that of right node. We have populated entire tree in this way and thus nodes are arranged in a sorted manner. Now iterating through the entire tree is easy and can be done simply visiting left sub tree then the node value and then right sub tree. This way we can print all the nodes in the tree.
Node LookupWe can also lookup for a node by comparing the required value with left child then with its own node and then with right child. This iteration will start from root and will go recursively into the sub tree level till our node is found. This is the way to check if a the value is already present in the tree.
Finding Minimum ValueNodes in Binary Search Tree are arranged in such a way that left of any node contains the lesser value. In this way if we take the left most node in the max depth level then that would contain the least value. Our logic goes in the same way. We iterate to node->left untill we hit NULL then we can find the Min Value.
About our authors: Team EQA
You have viewed 1 page out of 248. Your C learning is 0.00% complete. Login to check your learning progress.
Learn on Youtube