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.