In this tutorial, I am going to discuss binary tree inorder traversal without recursion.
Given a binary tree, write a code to print the Inorder traversal of a binary tree node values.
What is Binary Tree Inorder Traversal?
Traversing a tree means visiting each node of the tree exactly once. In inorder traversal, we visit the tree in following order.
i) Visit all the nodes of the left subtree.
ii) Visit root node.
iii) Visit all the nodes of the right subtree.
For example-
The Inorder traversal of given binary tree is 4, 6, 3, 7, 2, 5, 1.
Remember, we don’t have to use recursion. So, how do we print Inorder traversal of a binary tree using iterative approach. Do we need to use any additional data structure? Which data structure should we use?
Before writing, the iterative code of a binary tree inorder traversal. Let’s write it’s recursive version first.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
//Inorder Traversal using Recursion public static void inorderTraversalRecursion(TreeNode root) { //If root is null, then return if(root == null) { return; } //Traverse left subtree inorderTraversalRecursion(root.left); //Print root System.out.print(root.data + " "); //Traverse right subtree inorderTraversalRecursion(root.right); } |
To write it’s iterative version, which data structure should we use. Definitely, we use Stack for implementing inorder traversal without recursion.
Binary Tree Inorder Traversal using Stack – Algorithm
Let’s understand the algorithm of inorder traversal without recursion.
i) Declare an empty stack.
ii) Push the root node value into a stack and set root = root.left until root is not null.
So, in stack following value is pushed.
First operation is to Push 7, Now the value of Stack is S -> 7
In next step, Push 6, Stack S -> 7, 6
Push 4: Stack S -> 7, 6, 4
After this operation root node points to null. No further node is going to push.
iii) In next step, pop the value from stack. Print it’s value. Then, assign root to temp.right.
iv) Repeat step ii and iii until stack is empty or root is NULL.
Programming video tutorials on binary tree
Check if two binary trees are identical
Binary Tree Inorder Traversal without Recursion – Java Code
Let’s write a java code to implement Inorder traversal using stack.
|
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 |
//Binary tree inorder traversal using stack public class InorderTraversal { public static class TreeNode { int data; TreeNode left; TreeNode right; TreeNode(int data) { this.data = data; } } public static List<Integer> inorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); //Declare stack Stack<TreeNode> st = new Stack<>(); //While stack is not empty or root is not null while (!st.isEmpty() || root != null) { /* while the root is not null, traverse a left part until it is not reference to null. */ while (root != null) { st.add(root); root = root.left; } //Pop the node and add it's value in a list TreeNode temp = st.pop(); result.add(temp.data); //Check the right node reference root = temp.right; } return result; } public static TreeNode createBinaryTree() { TreeNode rootNode = new TreeNode(7); rootNode.left = new TreeNode(6); rootNode.right = new TreeNode(5); rootNode.left.left = new TreeNode(4); rootNode.left.right = new TreeNode(3); rootNode.right.left = new TreeNode(2); rootNode.right.right = new TreeNode(1); return rootNode; } public static void main(String[] args) { List<Integer> result = inorderTraversal(createBinaryTree()); //Traverse the list and print the result result.forEach( t -> System.out.print(t + " ")); } } |
Level Order Traversal of a Binary Tree
Binary tree preorder traversal
Binary Tree Inorder Traversal LeetCode Solution
LeetCode solution of a Binary Tree inorder traversal using stack.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
//Binary Tree Inorder Traversal Iterative public List<Integer> inorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); Stack<TreeNode> st = new Stack<>(); while(!st.isEmpty() || root != null) { while(root != null) { st.push(root); root = root.left; } TreeNode temp = st.pop(); result.add(temp.val); root = temp.right; } return result; } |
