**Question :**

WAP to Print Inorder Traversal of tree in O(n) time complexity.

**Example Binary Tree :**

**Solution :**

The problem is solved in both recursive and iterative way.

InOrder traversal of tree means to traverse the tree in left->root->right manner.

**Recursive Algorithm :**

Here we are traversing the left sub tree then root and then right sub tree.We are existing on null value of node .

**Iterative Algorithm :**

Since we need to print node 8 first.We are traversing form root till to the left most element of tree.We are inserting each element in a stack while traversing.After that we are checking if stack is empty or not.If it is not

empty we are printing the top element of the stack and poping the top element and making current element as right element of current element.

Let’s do a dry run.

Node 1 has left ? Yes then put Node 1 in stack and go to left of Node 1 i.e. Node 2.

Node 2 has left ? Yes then put Node 2 in stack and go to left of Node 2 i.e Node 4.

Node 4 has left ? Yes then put Node 1 in stack and go to left of Node 4 i.e Node 8.

Node 8 has left ? No then check if stack is empty.It is not empty.

Retrieve the top element of stack i.e Node 8.Print it.Pop it out.Enter its right node.But Node 8

has no right child.We print the top element of stack again as it is not empty.

Node 4 is printed.Node 4 has right child i.e Node 9.Node 9 is inserted into stack and it is printed.

This way gradually we reach the root i.e Node 1.

Node 1 has right child Node 3 and Node 3 has left child Node 6.

So from Node 8 to root 1 how the above algorithm works,similar form Node 6 same algorithm will work.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 |
package com.whizzchosen.dsalgo.binarytree; import java.util.Stack; class BinaryTree { int data; BinaryTree left; BinaryTree right; public BinaryTree(int data) { super(); this.data = data; this.left = null; this.right = null; } } public class InOrderBinaryTree { public static void main(String[] args) { BinaryTree root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); root.right.left = newNode(6); root.right.right = newNode(7); root.left.left.left = newNode(8); root.left.left.right = newNode(9); System.out.println("InOrder Traversal of Tree recurssively"); inOrderRecr(root); System.out.println(); System.out.println("InOrder Traversal of Tree iteravtively"); inOrderIter(root); } private static BinaryTree newNode(int data) { BinaryTree node = new BinaryTree(data); node.left = node.right = null; return node; } private static void inOrderRecr(BinaryTree root) { if (null == root) { return; } inOrderRecr(root.left); System.out.print(root.data + "\t"); inOrderRecr(root.right); } private static void inOrderIter(BinaryTree root) { if (null == root) { return; } Stack stack = new Stack(); BinaryTree current = root; boolean completeFlag = false; while (!completeFlag) { if (null != current) { stack.push(current); current = current.left; } else { if (stack.isEmpty()) { completeFlag = true; } else { current = stack.peek(); // top element of stack stack.pop(); System.out.print(current.data + "\t"); current = current.right; } } } } } |

1 2 3 4 5 6 7 |
OutPut: InOrder Traversal of Tree recurssively 8 4 9 2 5 1 6 3 7 InOrder Traversal of Tree iteravtively 8 4 9 2 5 1 6 3 7 |