A tree is an abstract data type which store elements hierarchically. With the exception of top element, each element in a tree has a parent element, and zero or more children elements. We generally call the top element root of the tree.
We can represent such a tree by a linked data structure, in which each node in an object. (Learn linked list, here). In addition to key and satellite data, each nodes contains left, right, and p that point to the nodes corresponding to its left child, right child, and parent respectively. if a child or parent is missing, the appropriate value contains the null value. The root node is the only node in the tree whose parent is null.
On average a tree is more efficient if we need to perform many different types of operations. Time needed to perform an operation on a tree is O(log N). Now let’s talk about what is Binary Search Tree (BST).
Binary Search Tree (BST)
Formally, we define a binary search tree to be a set of nodes storing elements in a parent-child relationship. For binary search tree, every node has maximum two children. middle node is called parent, and less value than parent is the left child, as well as greater value than parent is the right child. In BST, a node might have two maximum number of children. However, a child might have only one child or no child. Node with no child is called leaf.
The reason of using binary search tree that insertion or deletion of elements in the tree is very first. Searching an element in binary search tree is also very first. The binary tree can be balanced or unbalanced.
For an unbalanced tree it might look more like a long list of elements, and less like a tree. Therefore insertion, deletion, or even searching data will no longer be so fast in unbalanced tree. Ordered data normally creates an unbalanced tree. Thus there are algorithms that ensure that our tree stays valid, which is that roughly same amount of nodes will have both left and right side of subtree.
Traversing Of BST
Traversing means visit through trees. There are three way we can visit throughout the tree.
- Inorder Traversing – we visit the left node first, then the parent node, and then the right node.
- Preorder Traversing – Here, we visit the root node first, then the left node, and lastly the right node.
- Postorder Traversing – and in postorder traversal we visit the left node first, then the right node, and lastly the parent node or root node.
In BST we typically want to do inorder traversal. Because This allows to print the nodes tree inorder.
Next we will see the implementation of binary search tree here >>