Binary tree – An introduction

0 / 1477
Binary search tree

 

Binary Trees:

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.

Binary tree

Binary tree

 

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

Binary search tree

Binary search tree

 

 

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

[gistpen id=”824″]

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.

[gistpen id=”841″]

 

Stay tuned for more interesting programming stuff.

 

Comments

comments


An avid reader, responsible for generating creative content ideas for golibrary.co. His interests include algorithms and programming languages. Blogging is a hobby and passion.
loading...

Related Posts