Traversing a tree using Preorder 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;


/**
 * Traversing a tree using Preorder traveral iteratively
 * Preorder ==> Node, Left,Right
 * Time Complexity: O(n), Space Complexity: O(n)
 * @author Arun.Singh
 *
 */
public class PreorderTraversalIteration {
public ArrayList<Integer> preorderTraversal(BinaryTreeNode root) {
ArrayList<Integer> res = new ArrayList<Integer>();
if (root == null) {
return res;
}
Stack<BinaryTreeNode> s = new Stack<BinaryTreeNode>();
s.push(root);
while (!s.isEmpty()) {
BinaryTreeNode tmp = s.pop();
res.add(tmp.getData());
// pay more attention to this sequence
if (tmp.getRight() != null)
s.push(tmp.getRight());
if (tmp.getLeft() != null)
s.push(tmp.getLeft());
}
return res;
}

// [1, 2, 4, 5, 3, 6, 7]
public static void main(String[] args) {
System.out.println(new PreorderTraversalIteration().preorderTraversal(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.