Binary Tree Postorder Traversal

Write a program to find the Binary Tree Postorder Traversal.

Example 1:

Input: root = [1,2]
Output: [2,1]

Example 2:

Input: root = [1,null,2,3]
Output: [3,2,1]

Approach 1: Recursive

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class BinaryTreePostorderTraversalRecursion {
    public static void main(String[] args) {
        TreeNode tree = new TreeNode(1);
        tree.right = new TreeNode(2);
        tree.right.left = new TreeNode(3);
        postorder(tree);
        System.out.println("Tree Postorder is " + Arrays.asList(result));
    }

    static List<Integer> result = new ArrayList<>();

    public static void postorder(TreeNode root) {
        if (root == null)
            return;

        // visit left node
        postorder(root.left);
        // visit right node
        postorder(root.right);
        // Add root value
        result.add(root.val);

    }
}
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

// Time Complexity: O(n)

C++

#include <bits/stdc++.h>
using namespace std;
//struct for treenode
struct TreeNode{
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int data)
    {
        this->data=data;
        this->left=NULL;
        this->right=NULL;
    }
};
//Function to find postorder Traversal
//of tree
void postorderTraversal(TreeNode *root)
{
    //Base Case
    if(root==NULL)
       return;
   
    //visit left subtree
    postorderTraversal(root->left);
    //visit right subtree
    postorderTraversal(root->right);
     //print root data
    cout<<root->data<<" ";
}
int main()
{
    TreeNode *tree=new TreeNode(1);
    tree->right=new TreeNode(2);
    tree->right->left=new TreeNode(3);
    cout<<"Postorder Traversal\n";
    postorderTraversal(tree);
    return 0;
}
//Time Complexity: O(n)

Approach 2: Iterative

C++

#include <bits/stdc++.h>
using namespace std;
//struct for treenode
struct TreeNode{
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int data)
    {
        this->data=data;
        this->left=NULL;
        this->right=NULL;
    }
};
//Function to find postorder Traversal
//of tree
vector<int> postorderTraversal(TreeNode *root)
{
    vector<int> res;
    if(root==NULL)
       return res;
    stack<TreeNode *> st;
    st.push(root);
    while(!st.empty())
      {
            TreeNode *temp=st.top();
            res.push_back(temp->data);
            st.pop();
            if(temp->left)
                 st.push(temp->left);
             if(temp->right)
                 st.push(temp->right);
          
      }
      reverse(res.begin(),res.end());
     return res;
}
int main()
{
    TreeNode *tree=new TreeNode(1);
    tree->right=new TreeNode(2);
    tree->right->left=new TreeNode(3);
    cout<<"Postorder Traversal\n";
    vector<int> res=postorderTraversal(tree);
    int n=res.size();
    for(int i=0;i<n;i++)
       cout<<res[i]<<" ";
    
    return 0;
}
//Time Complexity: O(n)