From the blow figure , it is clear that a binary tree is a tree of nodes where each node contains a left pointer, a right pointer and a data. The “root” pointer points to the topmost node in the tree. The left pointer points to left side of sub-trees while right pointer points to right side of sub-trees.

biatryThe above figure represents generalized form of binary tree where each node has up to two leaves ( children ). It is simply representation of tree data structure.A binary tree where the left child contains only nodes with values less than the parent node, and where the right child only contains nodes with values greater than or equal to the parent node, is called Binary search tree.

The figure can be converted to Binary search tree as below.

bsearchBinary search trees are used in many search applications.

How to represents binary tree in c/c++

struct node {
struct node* left;
int data;
struct node* right;
}

Now let us implement following operations on binary search tree. ( duplicate data is allowed )

  • insert()
  • In_order_traverse()
  • Pre_order_order_traverse()
  • post_order_traverse()

Ref: http://en.wikipedia.org/wiki/Binary_tree