Postorder Traversal

Problem

Given a binary tree, find the Postorder Traversal of it.

For Example, the postorder traversal of the following tree is: 5 10 39 1

      1
    /   \
  10     39
 /
5

Examples:

Example 1:

Input:
        19
     /     \
    10      8
  /    \
 11    13
Output: 11 13 10 8 19

Example 2:

Input:
          11
         /
       15
      /
     7
Output: 7 15 11

Your task:

You don't need to read input or print anything. Your task is to complete the function postOrder() that takes root node as input and returns an array containing the postorder traversal of the given Binary Tree.

• Expected Time Complexity: $O(N)$
• Expected Auxiliary Space: $O(N)$

Constraints:

• $1 <=$ Number of nodes $<= 10^5$
• $0 <=$ Data of a node $<= 10^5$

Solution

Python

def postOrder(root):
    arr = []
    def traverse(node):
        if node is None:
            return
        traverse(node.left)
        traverse(node.right)
        arr.append(node.data)
    traverse(root)
    return arr

Java

ArrayList<Integer> postOrder(Node root) {
    ArrayList<Integer> arr = new ArrayList<>();
    traverse(root, arr);
    return arr;
}

void traverse(Node node, ArrayList<Integer> arr) {
    if (node == null)
        return;
    traverse(node.left, arr);
    traverse(node.right, arr);
    arr.add(node.data);
}

C++

void traverse(Node* node, vector<int>& result);

vector <int> postOrder(Node* root) {
    vector<int> result;
    traverse(root, result);
    return result;
}

void traverse(Node* node, vector<int>& result) {
    if (node == nullptr)
        return;
    traverse(node->left, result);
    traverse(node->right, result);
    result.push_back(node->data);
}

• Time Complexity: $O(N)$
• Auxiliary Space: $O(N)$