This post talks about InOrder traversal of binary tree implementation in Java
In InOrder traversal, the root is visited between the subtrees
InOrder traversal is defined as follows:
- Traverse the Left Subtree
- Visit the root
- Traverse the Right Subtree
InOrder, traversal can be implemented either recursive and iterative approach. Both Approaches have shown below:
Recursive Approach:
|
1 2 3 4 5 6 7 8 9 10 11 |
/** * Recursive method for Binary Tree inOrder Processing * @param root Node */ public void preOrderRecursive(Node<E> root) { if(root != null) { preOrderRecursive(root.left); System.out.print(root.data+" "); preOrderRecursive(root.right); } } |
Time Complexity: O(n) and Space Complexity: O(n)
Non-Recursive Approach:
The non-recursive version of InOrder traversal is similar to preorder. The only change is instead of processing the node before going to the left subtree, process it after popping.which is indicated after completion of left subtree processing.
|
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 |
/** * Iterative method for Binary Tree inOrder Processing * @param root Node */ public ArrayList<Node<E>> inOrderIterative(Node<E> root) { ArrayList<Node<E>> inOrderList = new ArrayList<>(); if(root == null) { return inOrderList; } Stack<Node<E>> stack = new Stack<>(); Node<E> currentNode = root; boolean done = false; while(!done) { if(currentNode != null) { stack.push(currentNode); currentNode = currentNode.left; }else { if(stack.isEmpty()) { done = true; }else { currentNode = stack.pop(); inOrderList.add(currentNode); currentNode = currentNode.right; } } } return inOrderList; } |
Time Complexity: O(n) and Space Complexity: O(n)
Below is the Complete Source code:
BinaryTree.java
|
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 |
package com.kkjavatutorials.tree; import java.util.ArrayList; import java.util.Stack; public class BinaryTree<E extends Comparable<? super E>> { /** * This internal class represents Node in Binary tree * @author KK JavaTutorials */ public static class Node<T> { //Data hold by Binary Tree Node public T data; //Left pointer/reference public Node<T> left; //Right pointer/reference public Node<T> right; public Node(T data) { this.data = data; } } /** * Recursive method for Binary Tree inOrder Processing * @param root Node */ public void inOrderRecursive(Node<E> root) { if(root != null) { inOrderRecursive(root.left); System.out.print(root.data+" "); inOrderRecursive(root.right); } } /** * Iterative method for Binary Tree inOrder Processing * @param root Node */ public ArrayList<Node<E>> inOrderIterative(Node<E> root) { ArrayList<Node<E>> inOrderList = new ArrayList<>(); if(root == null) { return inOrderList; } Stack<Node<E>> stack = new Stack<>(); Node<E> currentNode = root; boolean done = false; while(!done) { if(currentNode != null) { stack.push(currentNode); currentNode = currentNode.left; }else { if(stack.isEmpty()) { done = true; }else { currentNode = stack.pop(); inOrderList.add(currentNode); currentNode = currentNode.right; } } } return inOrderList; } } |
ClientTest.java
|
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 |
package com.kkjavatutorials.client; import java.util.ArrayList; import com.kkjavatutorials.tree.BinaryTree; import com.kkjavatutorials.tree.BinaryTree.Node; /** * Client Program to test inOrder Processing of Binary Tree * @author KK JavaTutorials */ public class ClientTest { public static void main(String[] args) { //Create an Instance of BinaryTree BinaryTree<Integer> binaryTree = new BinaryTree<>(); //Root Node Node<Integer> rootNode = new Node<Integer>(1); Node<Integer> secondNode = new Node<Integer>(2); Node<Integer> thirdNode = new Node<Integer>(3); Node<Integer> fourthNode = new Node<Integer>(4); Node<Integer> fifthNode = new Node<Integer>(5); Node<Integer> sixthNode = new Node<Integer>(6); Node<Integer> seventhNode = new Node<Integer>(7); //Setting Left and right of root Node rootNode.left = secondNode; rootNode.right = thirdNode; rootNode.left.left = fourthNode; rootNode.left.right = fifthNode; rootNode.right.left = sixthNode; rootNode.right.right = seventhNode; //Call for preOrder processing System.out.println(".....Binary Tree InOrder Processing output using Recursive method...."); binaryTree.inOrderRecursive(rootNode); System.out.println(); System.out.println(".....Binary Tree InOrder Processing output using Iterative method...."); ArrayList<Node<Integer>> inOrderIterative = binaryTree.inOrderIterative(rootNode); for (Node<Integer> node : inOrderIterative) { System.out.print(node.data+" "); } } } |
The output of This Program:
…..Binary Tree InOrder Processing output using Recursive method….
4 2 5 1 6 3 7
…..Binary Tree InOrder Processing output using Iterative method….
4 2 5 1 6 3 7
You May Also Like:
Introduction to Tree Data Structure
Introduction to Binary Tree
Structure of Binary Trees
Operations and use of Binary Trees
Binary Tree Traversals
PreOrder traversal of binary tree implementation in Java
PostOrder traversal of binary tree implementation in Java
That’s all about InOrder traversal of binary tree implementation in Java?
If you have any feedback or suggestion please feel free to drop in below comment box.