Java Binary Tree Preorder Traversal
Chapter:
Interview Programs
Last Updated:
04-11-2016 15:09:39 UTC
Program:
/* ............... START ............... */
import java.util.Stack;
public class JavaPreorderTraversal {
public static class TreeNode {
int data;
TreeNode left;
TreeNode right;
TreeNode(int data) {
this.data = data;
}
}
public void preorder(TreeNode root) {
if (root != null) {
System.out.printf("%d ", root.data);
preorder(root.left);
preorder(root.right);
}
}
public void preorderIter(TreeNode root) {
if (root == null)
return;
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
while (!stack.empty()) {
TreeNode n = stack.pop();
System.out.printf("%d ", n.data);
if (n.right != null) {
stack.push(n.right);
}
if (n.left != null) {
stack.push(n.left);
}
}
}
public static void main(String[] args) {
JavaPreorderTraversal bi = new JavaPreorderTraversal();
TreeNode rootNode = createBinaryTree();
System.out.println("Using Recursive solution:");
bi.preorder(rootNode);
System.out.println();
System.out.println("-------------------------");
System.out.println("Using Iterative solution:");
bi.preorderIter(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;
}
}
/* ............... END ............... */
Output
Using Recursive solution:
40 20 10 30 60 50 70
-------------------------
Using Iterative solution:
40 20 10 30 60 50 70
Notes:
-
In PreOrder traversal,each node is processed before either of its sub-trees.In simpler words,Visit each node before its children.
- Steps for PreOrder traversal are:
- Visit the node.
- Traverse the left subtree in PreOrder.
- Traverse the right subtree in PreOrder.
Tags
Binary Tree Preorder Traversal, Java, Interview Programs