## Thursday, April 5, 2012

### Inorder Traversal of Binary Search Tree

To traverse a non-empty tree in inorder the following steps are followed recursively.
• Visit the Root
• Traverse the left subtree
• Traverse the right subtree
The inorder traversal of the tree shown below is as follows.

Algorithm
``` ```

`The algorithm for inorder traversal is as follows. `

`Struct node`
`{ `
`struct node * lc; `
`int data; `
`struct node * rc; `
`}; `

`void inorder(struct node * root); `
`{ `
`if(root != NULL) `
`{ `
`inorder(root-> lc); `
```printf("%d\t",root->data); ```
`inorder(root->rc); `
`} `
`} `

```So the function calls itself recursively and carries on the traversal. ```

### Binary search tree and its implementation

Binary tree

A tree is a finite set of nodes having a distinct node called root.

Binary Tree is a tree which is either empty or has at most two subtrees, each of the subtrees also being a binary tree. It means each node in a binary tree can have 0, 1 or 2 subtrees. A left or right subtree can be empty.
A binary tree is made of nodes, where each node contains a "left" pointer, a "right" pointer, and a data element. The "root" pointer points to the topmost node in the tree. The left and right pointers point to smaller "subtrees" on either side. A null pointer represents a binary tree with no elements -- the empty tree. The formal recursive definition is: a binary tree is either empty (represented by a null pointer), or is made of a single node, where the left and right pointers (recursive definition ahead) each point to a binary tree.

Representation of Binary Tree

The structure of each node of a binary tree contains one data field and two pointers, each for the right & left child. Each child being a node has also the same structure.

``` ```
```Struct node { struct node *lc ; /* points to the left child */ int data; /* data field */ struct node *rc; /* points to the right child */ }```

1. Array Representation of Binary Tree:

A single array can be used to represent a binary tree.
For these nodes are numbered / indexed according to a scheme giving 0 to root. Then all the nodes are numbered from left to right level by level from top to bottom. Empty nodes are also numbered. Then each node having an index i is put into the array as its ith element.
In the figure shown below the nodes of binary tree are numbered according to the given scheme.

The figure shows how a binary tree is represented as an array. The root 3 is the 0 th element while its left child 5 is the 1 st element of the array. Node 6 does not have any child so its children ie 7 th & 8 th element of the array are shown as a Null value.
It is found that if n is the number or index of a node, then its left child occurs at (2n + 1) th position & right child at (2n + 2) th position of the array. If any node does not have any child, then null value is stored at the corresponding index of the array.

``` ```
`/* Prorgram to implement the above array representation * /`
``` ```
`Struct node `
`{ `
`struct node * lc; `
`int data; `
`struct node * rc; `
`}; `
`struct node * buildtree(int); /* builds the tree*/ `
```void inorder(struct node *); /* Traverses the tree in inorder*/ ```
```int a[]={ 3,5,9,6,8,20,10,/0,/0,9,/0,/0,/0,/0,/0,/0,/0,/0,/0,/0,/0}; ```

`void main( ) `
`{ `
`struct node * root; `
`root= buildtree(0); `
`printf(“\n Inorder Traversal”); `
`inorder(root); `
`getch( ); `
`} `

`struct node * buildtree(int n); `
`{ `
`struct node * temp=NULL; `
`if( a[n] != NULL) `
`{ `
`temp = (struct node *) malloc(sizeof(struct node)); `
`temp-> lc=buildtree(2n + 1); `
`temp-> data= a[n]; `
`temp-> rc=buildtree(2n + 2); `
`} `
`return temp; `
`} `

`void inorder(struct node * root); `
`{ `
`if(root != NULL) `
`{ `
`if(root!= NULL) `
`{ `
`inorder(root-> lc); `
`printf(“%d\t”,root->data); `
`inorder(root->rc); `
`} `
`} `

`Courtesy : NPTEL `
``` ```

``` ```