import java.util.Stack;
//Postorder Tree Traversals : Iterative
Model(Non-Recursive way)
class BinaryTreePostOrderTraversalIterativeModel {
class TreeNode {
TreeNode left, right;
int data; // considering integer data.
public TreeNode(int dataItem) {
this.data = dataItem;
left = null;
right = null;
}
}
TreeNode root;
BinaryTreePostOrderTraversalIterativeModel()
{
root = null;
}
void printPostOrderTraversal(TreeNode treeNode) {
if(treeNode == null)
return;
//Left, Right, Data
Stack<TreeNode> s = new Stack<TreeNode>();
s.push(root);
while (!s.isEmpty()) {
TreeNode
current = s.peek();
if ( current.left == null || current.right == null) {
TreeNode
node = s.pop();
System.out.println(node.data);
} else {
if(current.right != null){
s.push(current.right);
current.right = null;
}
if(current.left != null){
s.push(current.left);
current.left = null;
}
}
}
}
void printPostOrder() {
printPostOrderTraversal(root);
}
public static void main(String[] args) {
BinaryTreePostOrderTraversalIterativeModel
tree = new
BinaryTreePostOrderTraversalIterativeModel();
tree.root = new TreeNode(1);
tree.root.left = new TreeNode(2);
tree.root.right = new TreeNode(3);
tree.root.left.left = new TreeNode(4);
tree.root.left.right = new TreeNode(5);
tree.root.right.left = new TreeNode(6);
tree.root.right.right = new TreeNode(7);
tree.printPostOrder();
}
}
//Time Complexity: O(n). Space Complexity: O(n).
|
Thanks..!!
No comments:
Post a Comment