"After popping of element from stack - check whether popped element and right child of stack top element are same or not" - if same we have covered both left and right subtree, pop one more element and display otherwise, process right child.
Node visit sequence in postorder - 56 78 11 43 23 98 12 18 12
Algorithm:-
- If tress is not empty(root is not null), push all right child followed by current node into stack.
- Loop until stack is not empty. Pop an element and check whether popped element has right child or not -
If right child exist and poppedElement.rightChild == stackTop, then process right child before(pop stack and puch popped element back to stack)
Otherwise, we have processed both left and right child - display popped element - Repeat 1 to 3, and exit outer loop when stack is empty.
- Process/display root of the tree.
Sample code for postorder traversal of binary tree in Java - Using one stack
public String iterativePostorderTraversalUsingOneStack(Node root) {
StringBuffer sbf = new StringBuffer();
/* java.util.Stack */
Stack<Node> stack = new Stack<>();
if (root != null) {
while (true) {
/*
* Traverse tree until left child exist and push right and
* current node into stack
*/
while (root != null) {
if (root.rightChild != null)
stack.push(root.rightChild);
stack.push(root);
root = root.leftChild;
}
/* Pop an element from stack */
root = stack.pop();
/* Exit outer loop, if stack is empty */
if (stack.isEmpty()) {
break;
} else {
/*
* check whether root's right child exist or not .If exist
* process it before root
*/
if (root.rightChild != null
&& root.rightChild.equals(stack.peek())) {
stack.pop();
stack.push(root);
root = root.rightChild;
} else {
sbf.append(root.getData() + " ");
root = null;
}
}
}
}
/* process root of the tree,once stack is empty and root is not null*/
if (root != null) {
sbf.append(root.data);
}
return sbf.toString();
}
Complete sample program of postorder traversal of binary tree in Java - Using one stack
package com.devinline.trees; import java.util.Stack; public class IterativePostOrderUsingOneStack { public String iterativePostorderTraversalUsingOneStack(Node root) { StringBuffer sbf = new StringBuffer(); /* java.util.Stack */ Stack<Node> stack = new Stack<>(); if (root != null) { while (true) { /* * Traverse tree until left child exist and push right and * current node into stack */ while (root != null) { if (root.rightChild != null) stack.push(root.rightChild); stack.push(root); root = root.leftChild; } /* Pop an element from stack */ root = stack.pop(); /* Exit outer loop, if stack is empty */ if (stack.isEmpty()) { break; } else { /* * check whether root's right child exist or not .If exist * process it before root */ if (root.rightChild != null && root.rightChild.equals(stack.peek())) { stack.pop(); stack.push(root); root = root.rightChild; } else { sbf.append(root.getData() + " "); root = null; } } } } /* process root of the tree,once stack is empty */ if (root != null) { sbf.append(root.data); } return sbf.toString(); } public static void main(String[] args) { IterativePostOrderUsingOneStack ipo2SObj = new IterativePostOrderUsingOneStack(); Node root = ipo2SObj.new BinaryTree().createTree(); String nodesStr = ipo2SObj .iterativePostorderTraversalUsingOneStack(root); System.out.println("Postorder traversal is: " + nodesStr); } class BinaryTree { Node root; public BinaryTree() { root = null; } public Node createTree() { if (root == null) { root = new Node(12); } root.setLeftChild(new Node(23)); root.setRightChild(new Node(18)); root.getLeftChild().setLeftChild(new Node(11)); root.getLeftChild().setRightChild(new Node(43)); root.getRightChild().setLeftChild(new Node(12)); root.getLeftChild().getLeftChild().setLeftChild(new Node(56)); root.getLeftChild().getLeftChild().setRightChild(new Node(78)); root.getRightChild().getLeftChild().setRightChild(new Node(98)); return root; } } class Node { private int data; private Node leftChild; private Node rightChild; public Node(int data) { this.data = data; leftChild = null; rightChild = null; } public int getData() { return data; } public void setData(int data) { this.data = data; } public Node getLeftChild() { return leftChild; } public void setLeftChild(Node leftChild) { this.leftChild = leftChild; } public Node getRightChild() { return rightChild; } public void setRightChild(Node rightChild) { this.rightChild = rightChild; } } }
Postorder traversal is: 56 78 11 43 23 98 12 18 12
===============================
0 comments:
Post a Comment