This post talks about PostOrder traversal of binary tree implementation in Java
In postOrder traversal, the root is visited after both left and right subtrees.
PostOrder traversal is defined as follows:
- Traverse the Left Subtree
- Traverse the Right Subtree
- Visit the root
PostOrder traversal can be implemented either recursive and iterative approach. Both Approaches have shown below:
Recursive Approach:
1 2 3 4 5 6 7 8 9 10 11 |
/** * Recursive method for Binary Tree postOrder Processing * @param root Node */ public void postOrderRecursive(Node<E> root) { if(root != null) { postOrderRecursive(root.left); postOrderRecursive(root.right); System.out.print(root.data+" "); } } |
Time Complexity: O(n) and Space Complexity: O(n)
Non-Recursive Approach:
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 |
/** * Iterative method for Binary Tree postOrder Processing * @param root Node */ public ArrayList<Node<E>> postOrderIterative(Node<E> root) { ArrayList<Node<E>> inOrderList = new ArrayList<>(); if(root == null) { return inOrderList; } Stack<Node<E>> stack = new Stack<>(); stack.push(root); Node<E> prev = null; while(!stack.isEmpty()) { Node<E> curr = stack.peek(); if(prev == null || prev.left == curr || prev.right == curr) { /*traverse from top to bottom and if curr has left child or right child then push into the stack otherwise pop out*/ if(curr.left !=null) stack.push(curr.left); else if(curr.right != null) stack.push(curr.right); }else if(curr.left == prev) { if(curr.right != null) stack.push(curr.right); }else { inOrderList.add(curr); stack.pop(); } prev = curr; } return inOrderList; } |
Time Complexity: O(n) and Space Complexity: O(n)
Below is the Complete Source code:
BinaryTree.java
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 |
package com.kkjavatutorials.tree; import java.util.ArrayList; import java.util.Stack; public class BinaryTree<E extends Comparable<? super E>> { /** * This internal class represents Node in Binary tree * @author KK JavaTutorials */ public static class Node<T> { //Data hold by Binary Tree Node public T data; //Left pointer/reference public Node<T> left; //Right pointer/reference public Node<T> right; public Node(T data) { this.data = data; } } /** * Recursive method for Binary Tree postOrder Processing * @param root Node */ public void postOrderRecursive(Node<E> root) { if(root != null) { postOrderRecursive(root.left); postOrderRecursive(root.right); System.out.print(root.data+" "); } } /** * Iterative method for Binary Tree postOrder Processing * @param root Node */ public ArrayList<Node<E>> postOrderIterative(Node<E> root) { ArrayList<Node<E>> inOrderList = new ArrayList<>(); if(root == null) { return inOrderList; } Stack<Node<E>> stack = new Stack<>(); stack.push(root); Node<E> prev = null; while(!stack.isEmpty()) { Node<E> curr = stack.peek(); if(prev == null || prev.left == curr || prev.right == curr) { /*traverse from top to bottom and if curr has left child or right child then push into the stack otherwise pop out*/ if(curr.left !=null) stack.push(curr.left); else if(curr.right != null) stack.push(curr.right); }else if(curr.left == prev) { if(curr.right != null) stack.push(curr.right); }else { inOrderList.add(curr); stack.pop(); } prev = curr; } return inOrderList; } } |
ClientTest.java
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 |
package com.kkjavatutorials.client; import java.util.ArrayList; import com.kkjavatutorials.tree.BinaryTree; import com.kkjavatutorials.tree.BinaryTree.Node; /** * Client Program to test postOrder Processing of Binary Tree * @author KK JavaTutorials */ public class ClientTest { public static void main(String[] args) { //Create an Instance of BinaryTree BinaryTree<Integer> binaryTree = new BinaryTree<>(); //Root Node Node<Integer> rootNode = new Node<Integer>(1); Node<Integer> secondNode = new Node<Integer>(2); Node<Integer> thirdNode = new Node<Integer>(3); Node<Integer> fourthNode = new Node<Integer>(4); Node<Integer> fifthNode = new Node<Integer>(5); Node<Integer> sixthNode = new Node<Integer>(6); Node<Integer> seventhNode = new Node<Integer>(7); //Setting Left and right of root Node rootNode.left = secondNode; rootNode.right = thirdNode; rootNode.left.left = fourthNode; rootNode.left.right = fifthNode; rootNode.right.left = sixthNode; rootNode.right.right = seventhNode; //Call for preOrder processing System.out.println(".....Binary Tree postOrder Processing output using Recursive method...."); binaryTree.postOrderRecursive(rootNode); System.out.println(); System.out.println(".....Binary Tree postOrder Processing output using Iterative method...."); ArrayList<Node<Integer>> postOrderIterative = binaryTree.postOrderIterative(rootNode); for (Node<Integer> node : postOrderIterative) { System.out.print(node.data+" "); } } } |
The output of This Program:
…..Binary Tree postOrder Processing output using Recursive method….
4 5 2 6 7 3 1
…..Binary Tree postOrder Processing output using Iterative method….
4 5 2 6 7 3 1
You May Also Like:
Introduction to Tree Data Structure
Introduction to Binary Tree
Structure of Binary Trees
Operations and use of Binary Trees
Binary Tree Traversals
PreOrder traversal of binary tree implementation in Java
InOrder traversal of binary tree implementation in Java
That’s all about PostOrder traversal of binary tree implementation in Java?
If you have any feedback or suggestion please feel free to drop in below comment box.