If you want to practice data structure and algorithm programs, you can go through 100+ java coding interview questions.
This is 3rd part of java binary tree tutorial.
PostOrder traversal
- Traverse the
left subtree
in PostOrder. - Traverse the
right subtree
in PostOrder. Visit
the 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
s
and setcurrentNode =root
. - while
currentNode
is not NULL Do following- Push
currentNode 's right child
and thencurrentNode
to stacks
- Set
currentNode=currentNode.left
- Push
- Pop a node from stack
s
and set it tocurrentNode
- If the popped node has a
right child
and the right child is at top of stack, thenremove
the right child from stack, push thecurrentNode
back and setcurrentNode
ascurrentNode 's right child
. - Else print
currentNode's data
and setcurrentNode
as 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; } } } |
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 |
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; } } |
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
What happens when the last left node does not have any children?