If you want to practice data structure and algorithm programs, you can go through Top 100+ data structure and algorithm interview questions.
This is 4th part of java binary tree tutorial.
In this post, we will see about InOrder binary tree traversal in java.
InOrder traversal:
In InOrder traversal,each node is processed between subtrees.In simpler words,Visit left subtree, node and then right subtree.
Steps for InOrder traversal are:
- Traverse the left subtree in InOrder.
- Visit the node.
- Traverse the right subtree in InOrder.
There can be two ways of implementing it
- Recursive
- Iterative
Recursive solution
Recursive solution is very straight forward.Below diagram will make you understand recursion better.
Code for recursion will be:
|
1 2 3 4 5 6 7 8 9 10 11 |
// Recursive Solution public void inOrder(TreeNode root) { if(root != null) { inOrder(root.left); //Visit the node by Printing the node data System.out.printf("%d ",root.data); inOrder(root.right); } } |
Iterative solution
For recursion, we use implicit stack. So here to convert recursive solution to iterative, we will use explicit stack.
Steps for iterative solution:
- Create an empty stack s and Initialize currentNode as root
- Push the currentNode to s and set currentNode = currentNode.left until currentNode is NULL
- If
currentNode is NULL and
s is not empty then
- Pop the top node from stack s and print it
- set currentNode = currentNode.right
- go to step 2
- If stack is empty and currentNode is also null then we are done with it
|
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 |
// Iterative solution public void inOrderIter(TreeNode root) { if(root == null) return; Stack<TreeNode> s = new Stack<TreeNode>(); TreeNode currentNode=root; while(!s.empty() || currentNode!=null){ if(currentNode!=null) { s.push(currentNode); currentNode=currentNode.left; } else { TreeNode n=s.pop(); System.out.printf("%d ",n.data); currentNode=n.right; } } } |
Lets create java program for InOrder traversal:
|
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 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 |
package org.arpit.java2blog.binarytree; import java.util.Stack; public class BinaryTreeInOrder { public static class TreeNode { int data; TreeNode left; TreeNode right; TreeNode(int data) { this.data=data; } } // Recursive Solution public void inOrder(TreeNode root) { if(root != null) { inOrder(root.left); //Visit the node by Printing the node data System.out.printf("%d ",root.data); inOrder(root.right); } } // Iterative solution public void inOrderIter(TreeNode root) { if(root == null) return; Stack<TreeNode> s = new Stack<TreeNode>(); TreeNode currentNode=root; while(!s.empty() || currentNode!=null){ if(currentNode!=null) { s.push(currentNode); currentNode=currentNode.left; } else { TreeNode n=s.pop(); System.out.printf("%d ",n.data); currentNode=n.right; } } } public static void main(String[] args) { BinaryTreeInOrder bi=new BinaryTreeInOrder(); // Creating a binary tree TreeNode rootNode=createBinaryTree(); System.out.println("Using Recursive solution:"); bi.inOrder(rootNode); System.out.println(); System.out.println("-------------------------"); System.out.println("Using Iterative solution:"); bi.inOrderIter(rootNode); } public static TreeNode createBinaryTree() { TreeNode rootNode =new TreeNode(40); TreeNode node20=new TreeNode(20); TreeNode node10=new TreeNode(10); TreeNode node30=new TreeNode(30); TreeNode node60=new TreeNode(60); TreeNode node50=new TreeNode(50); TreeNode node70=new TreeNode(70); rootNode.left=node20; rootNode.right=node60; node20.left=node10; node20.right=node30; node60.left=node50; node60.right=node70; return rootNode; } } |
Run above program and you will get following output:
Using Recursive solution:
10 20 30 40 50 60 70
————————-
Using Iterative solution:
10 20 30 40 50 60 70
10 20 30 40 50 60 70
————————-
Using Iterative solution:
10 20 30 40 50 60 70
Java Binary tree tutorial
- Binary tree in java
- Binary tree preorder traversal
- Binary tree postorder traversal
- Binary tree inorder traversal
- Binary tree level order traversal
- Binary tree spiral order traversal
- Binary tree reverse level order traversal
- Binary tree boundary traversal
- Print leaf nodes of binary tree
- Count leaf nodes in binary tree
- get maximum element in binary tree
- Print all paths from root to leaf in binary tree
- Print vertical sum of binary tree in java
- Get level of node in binary tree in java
- Lowest common ancestor(LCA) in binary tree in java
Please go through java interview programs for more such programs.
