Traversing a tree using Inorder traveral iteratively

package in.blogspot.arunj2ee.ds.tree.traversal;

import in.blogspot.arunj2ee.ds.tree.BinaryTreeNode;
import in.blogspot.arunj2ee.ds.tree.util.TreeUtil;

import java.util.ArrayList;
import java.util.Stack;

/**
 * Nice Implemnetation
 * Traversing a tree using Inorder traveral iteratively
 * Preorder ==> Left,Node,Right
 * Time Complexity: O(n), Space Complexity: O(n)
 * @author Arun.Singh
 *
 */
public class InorderTraversalIterative {
public static ArrayList<Integer> inorderTraversal(BinaryTreeNode root) {
ArrayList<Integer> res = new ArrayList<Integer>();
Stack<BinaryTreeNode> s = new Stack<BinaryTreeNode>();
BinaryTreeNode currentNode = root;
boolean done = false;
while (!done) {
if (currentNode != null) {
s.push(currentNode);
currentNode = currentNode.getLeft();
} else {
if (s.isEmpty()) {
done = true;
} else {
currentNode = s.pop();
res.add(currentNode.getData());
currentNode = currentNode.getRight();
}

}
}
return res;
}

//[4, 2, 5, 1, 6, 3, 7]
public static void main(String[] args) {
System.out.println(inorderTraversal(TreeUtil.makeSampleBinaryTree())
.toString());
}
}

========================================================================
Refer Core Classes: http://arunj2ee.blogspot.in/2017/05/tree-core-and-utility-classes.html
========================================================================

Share on Google Plus

About Admin

Arun is a JAVA/J2EE developer and passionate about coding and managing technical team.