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

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

Input:

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

## Solutions

### Method 1: Iteration

The

**pre-order**traversal of a binary tree can also be performed iteratively using a**Stack**.**Following is a simple stack-based iterative algorithm to perform pre-order traversal:**s -> empty stack while(not s.empty()) node -> s.pop() visit(node) if(node.right != null) s.push(node.right) if(node.left != null) s.push(node.left)

##### 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

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

**1)** print current-node

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

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

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

if(root==null) return; visit(root); preorder(root.left); preorder(root.right);

##### Complexity

The time complexity of this solution is

**O(n)**and space complexity is**O(n)**due to recursive calls.