FOR FREE MATERIALS

Introduction:

A binary tree is a special tree, where every node can have at most two children. One node designated as the root marks the beginning of the binary tree. In a binary tree, the child node on the left is called ‘left child node’ and the child node on the right is called the ‘right child node’.

A binary tree can either be empty or it may comprise a node called the ‘root’, a left sub-binary tree and right sub-binary tree, both of which acts like a binary tree.

 Tree traversal is the process to visit each and every node of a tree and display their values. There are three ways to traverse a binary tree

(a) In-order traversal

(b) Pre-order traversal

(c) Post-order traversal

(a) In-order traversal:

 In in-order traversal, the left sub-tree is visited first, then the root node followed by the right sub-tree. Every sub-tree is again considered to be a binary tree. 

Let us consider an example, in Fig 2, ‘5’ is the root node of the binary tree. In in-order traversal, at first the left sub-tree is considered , then the root node followed by the right sub-tree, untill all the nodes have been visited.

Thus the in-order traversal of the binary tree in Fig 2 will be 1,      2,      3,      5,      6,         4.

(a) Pre-order traversal:

 In pre-order traversal, the root node is visited first, then the left sub-tree followed by the right sub-tree. Every sub-tree is again considered to be a binary tree. 

 Let us consider an example, in Fig 2, ‘5’ is the root node of the binary tree. In pre-order traversal, at first the root node is considered , then the left sub-tree followed by the right sub-tree, untill all the nodes have been visited.

Thus the pre-order traversal of the binary tree in Fig 2 will be 5,      2,      1,      3,      6,         4

(a) Post-order traversal:

 In post-order traversal, the left sub-tree is visited first, then the right sub-tree followed by the root node . Every sub-tree is again considered to be a binary tree. 

 Let us consider an example, in Fig 2, ‘5’ is the root node of the binary tree. In post-order traversal, at first the left sub-tree is considered , then the right sub-tree followed by the root node, untill all the nodes have been visited.

Thus the post-order traversal of the binary tree in Fig 2 will be      1,      3,      2,      4,         6,      5.

Algorithm:

Input:

root which points to the root of the Binary Tree.

Output:

Binary Tree creation and then printing the tree in preorder, postorder and inorder using iteration.

Algo:

Step 1: Start

Step 2: Defining the create() function

l  Enter the value of the node.

l  Set temp[data]   <= value .

l  If left child of the node exists then,

(a) Set temp[left]  <= create().

l  If right child of the node exists then,

(a) Set temp[right]  <= ().

l  Return temp.

Step 3: Defining the preorder(temp) function

l If temp != NULL then,

(a) stack.push(temp).

(b) Repeat substeps while (stack is not empty)

Set t  <=  ().

Display(t[data]).

If t.right !=NULL then,

stack.push(t.right).

If t.left !=NULL then,

stack.push(t.left)

Step 4: Defining the inorder(temp) function

l  Repeat substeps while True

(a) Repeat substeps while temp!=NULL

stack.push(temp)

Set temp   <=       [left]

(b) If (stack is empty)

  break from loop

(c)

Set temp <= stack.pop()

(d) Display(temp[data]).

(e)

Set temp  <= temp[right].

Step 5: Defining the postorder(temp) function

l If temp != NULL then,

(a) stack1.push(temp).

(b) Repeat substeps while (stack1 is not empty)

Set t <=   stack1.pop()

stack2.push(t)

If t.right !=NULL then,

stack1.push(t.right).

If t.left !=NULL then,

stack1.push(t.left)

(c) Repeat substeps while (stack2 is not empty)

Display(stack2.pop()[data]).

Step 6: Stop