Binary Tree Postorder Traversal - The Coding Shala

Last Updated: 19-Jan-2021
Home >> Data Structures >> Binary Tree PostOrder Traversal

In this post, we will learn how to Traverse a Binary Tree in Post-Order.

Binary Tree Post-Order Traversal

Given a binary tree, return the postorder traversal of its nodes' values.

Example:
Input: [1,null,2,3]
1
\
2
/
3
Output: [3,2,1]

Post-Order Traversal of Binary Tree in Java

Approach 1

Using Recursion.

Java Program:

```/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> PostOrder = new ArrayList<Integer>();
if(root == null) return PostOrder;
return PostOrder;
}
}
```

Approach 2

Using Stack[DFS].

Java Program:

```/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<Integer>();
if(root == null) return ans;
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
while(!stack.empty()){
TreeNode curr = stack.pop();
if(curr.left != null) stack.push(curr.left);
if(curr.right != null) stack.push(curr.right);
}
return ans;
}
}
```

Other Posts You May Like