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.