Binary tree – An introduction
Today, in this blog we will discuss about binary trees. Binary tree is a data structure in which each node has two successors called the left and right child.
Below is a small image showing what a typical binary tree is like.
The above diagram just shows a binary tree which is different than a binary search tree. Difference between the two is the former is un-ordered and hence not fit for fast lookup of nodes however, binary search tree satisfies the criteria that if the child node is greater than the root, then it will be inserted to the right else to the left of the root node as shown in below diagram
Below is a small program that demonstrates creation of binary search tree and traversal , viz. inorder, preorder and postorder
C program for binary search tree
The above program simply uses the recursive approach in creating and traversing through the binary search tree.
insert() inserts the node data passed as argument to the right if its greater than the root node else to the left by calling itself recursively. It first allocates memory for the root node, if the tree is empty.
inorder(), preorder() and postorder() all use recursion whereas, the traversing is done by visiting left, root and right in case of inorder,
root, left and right in case of preorder & left, right and root in case of post order.
Here is the output of the code: – Btree – Output
We will now move a bit ahead and write code for searching and deleting a particular node from a binary search tree. The below program , traverses through the tree, until node is found, frees the node so that there are no memory leaks and returns.
Stay tuned for more interesting programming stuff.