If you want to practice data structure and algorithm programs, you can go through Top 100+ data structure and algorithm interview questions.
This is 3rd part of java binary tree tutorial.
In this post, we will see about PostOrder binary tree traversal in java.
PostOrder traversal
In PostOrder traversal, each node is processed after subtrees traversal.In simpler words,Visit left subtree, right subtree and then node.
Steps for PostOrder traversal are:
- Traverse the
left subtreein PostOrder. - Traverse the
right subtreein PostOrder. Visitthe node.
There can be two ways of implementing it
- Recursive
- Iterative
Recursive solution
Recursive solution is very straight forward.Below diagram will make you understand recursion better.
Code for recursion will be:
|
1 2 3 4 5 6 7 8 9 10 11 |
// Recursive Solution public void postOrder(TreeNode root) { if(root != null) { postOrder(root.left); postOrder(root.right); //Visit the node by Printing the node data System.out.printf("%d ",root.data); } } |
Iterative solution:
Steps for iterative solution:
- Create an empty stack
sand setcurrentNode =root. - while
currentNodeis not NULL Do following- Push
currentNode 's right childand thencurrentNodeto stacks - Set
currentNode=currentNode.left
- Push
- Pop a node from stack
sand set it tocurrentNode- If the popped node has a
right childand the right child is at top of stack, thenremovethe right child from stack, push thecurrentNodeback and setcurrentNodeascurrentNode 's right child. - Else print
currentNode's dataand setcurrentNodeas NULL.
- If the popped node has a
- Repeat steps 2 and 3 while stack is not empty.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
// Iterative solution public void postorderIter( TreeNode root) { if( root == null ) return; Stack<TreeNode> s = new Stack<TreeNode>( ); TreeNode current = root; while( true ) { if( current != null ) { if( current.right != null ) s.push( current.right ); s.push( current ); current = current.left; continue; } if( s.isEmpty( ) ) return; current = s.pop( ); if( current.right != null && ! s.isEmpty( ) && current.right == s.peek( ) ) { s.pop( ); s.push( current ); current = current.right; } else { System.out.print( current.data + " " ); current = null; } } } |
Lets create java program for postOrder traversal:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 |
package org.arpit.java2blog.binarytree; import java.util.Stack; public class BinaryTreePostOrder { public static class TreeNode { int data; TreeNode left; TreeNode right; TreeNode(int data) { this.data=data; } } // Recursive Solution public void postOrder(TreeNode root) { if(root != null) { postOrder(root.left); postOrder(root.right); //Visit the node by Printing the node data System.out.printf("%d ",root.data); } } // Iterative solution public void postorderIter( TreeNode root) { if( root == null ) return; Stack<TreeNode> s = new Stack<TreeNode>( ); TreeNode current = root; while( true ) { if( current != null ) { if( current.right != null ) s.push( current.right ); s.push( current ); current = current.left; continue; } if( s.isEmpty( ) ) return; current = s.pop( ); if( current.right != null && ! s.isEmpty( ) && current.right == s.peek( ) ) { s.pop( ); s.push( current ); current = current.right; } else { System.out.print( current.data + " " ); current = null; } } } public static void main(String[] args) { BinaryTreePostOrder bi=new BinaryTreePostOrder(); // Creating a binary tree TreeNode rootNode=createBinaryTree(); System.out.println("Using Recursive solution:"); bi.postOrder(rootNode); System.out.println(); System.out.println("-------------------------"); System.out.println("Using Iterative solution:"); bi.postorderIter(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; } } |
Run above program and you will get following output:
Using Recursive solution:
10 30 20 50 70 60 40
————————-
Using Iterative solution:
10 30 20 50 70 60 40
10 30 20 50 70 60 40
————————-
Using Iterative solution:
10 30 20 50 70 60 40
Java Binary tree tutorial
- Binary tree in java
- Binary tree preorder traversal
- Binary tree postorder traversal
- Binary tree inorder traversal
- Binary tree level order traversal
- Binary tree spiral order traversal
- Binary tree reverse level order traversal
- Binary tree boundary traversal
- Print leaf nodes of binary tree
- Count leaf nodes in binary tree
- get maximum element in binary tree
- Print all paths from root to leaf in binary tree
- Print vertical sum of binary tree in java
- Get level of node in binary tree in java
- Lowest common ancestor(LCA) in binary tree in java
Please go through java interview programs for more such programs.
What happens when the last left node does not have any children?