Given a binary tree, the task is to write an **iterative** and **recursive** solution to perform **in-order traversal** on it.

##### Example 1: Print in-order traversal of a Binary Tree

Input:

**Output: **2, 7, 5, 6, 11, 1, 9, 5, 9

## Solutions

### Method 1: Iteration

The **in-order traversal** of a binary tree can also be performed **iteratively** using a **Stack**.

Following is a simple stack-based iterative algorithm to perform in-order traversal:

s —> empty stack while (not s.isEmpty() or node != null) if (node != null) s.push(node) node —> node.left else node —> s.pop() visit(node) node —> node.right

##### Complexity

The time complexity of this solution is **O(n)** and space complexity is **O(n)** due to extra space required by stack.

### Method 2: Recursion

In-order traversal of a tree using recursion is extremely simple and straightforward, its a three step code:

**1)** traverse, left of current-node

**2)** print current-node

**3)** traverse, right of current-node

if, current is null, return; this will make the **base condition** for this program.

##### Complexity

The time complexity of this solution is **O(n) **and space complexity is **O(n)** due to recursive calls.