Binary Tree Postorder Traversal - Practice Coding Problems

Binary Tree Postorder Traversal - Problem

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

In postorder traversal, we visit nodes in the order: left subtree → right subtree → current node. This means we process all children before processing the parent node.

Note: You may implement this using either recursive or iterative approaches.

Input & Output

Example 1 — Basic Tree

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

› Output: [3,2,1]

💡 Note: Postorder visits left→right→root: node 3 (leaf), then node 2, finally root 1

Example 2 — Empty Tree

$ Input: root = []

› Output: []

💡 Note: Empty tree returns empty array

Example 3 — Single Node

$ Input: root = [1]

› Output: [1]

💡 Note: Single node tree: only root to process

Constraints

The number of nodes in the tree is in the range [0, 100]
-100 ≤ Node.val ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Binary tree with nodes [1,null,2,3]

Traversal Order

Visit left→right→root: 3, 2, then 1

Output Array

Collect node values: [3,2,1]

Key Takeaway

🎯 Key Insight: Postorder processes all children completely before touching the parent node

Asked in

G Google 45 a Amazon 38 M Microsoft 32 f Facebook 28

Binary tree postorder traversal visits nodes in left→right→root order. The recursive approach naturally follows this pattern, while the iterative approach uses a stack with result reversal. Best approach: Recursive for simplicity. Time: O(n), Space: O(h) where h is tree height.

Common Approaches

Approach	Time	Space	Notes
✓ Iterative with Stack	O(n)	O(h)	Use explicit stack to simulate recursion with reverse processing
Recursive Postorder	O(n)	O(h)	Simple recursive approach visiting left, right, then current node

Iterative with Stack — Algorithm Steps

Push root to stack
Pop node, add to result, push left then right
Continue until stack empty
Reverse result to get postorder

Visualization

Tap to expand

Step-by-Step Walkthrough

Forward Pass

Process root→right→left, collecting values

Stack Operations

Push children in left→right order

Reverse Result

Reverse collected values to get postorder

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct TreeNode* createNode(int val) {
    struct TreeNode* node = malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int* solution(struct TreeNode* root, int* returnSize) {
    *returnSize = 0;
    if (!root) return NULL;
    
    struct TreeNode* stack[1000];
    int* result = malloc(1000 * sizeof(int));
    int top = 0;
    int idx = 0;
    
    stack[top++] = root;
    
    while (top > 0) {
        struct TreeNode* node = stack[--top];
        result[idx++] = node->val;
        
        if (node->left) stack[top++] = node->left;
        if (node->right) stack[top++] = node->right;
    }
    
    // Reverse result
    for (int i = 0; i < idx / 2; i++) {
        int temp = result[i];
        result[i] = result[idx - 1 - i];
        result[idx - 1 - i] = temp;
    }
    
    *returnSize = idx;
    return result;
}

struct TreeNode* buildTree(char* input) {
    if (strlen(input) <= 2) return NULL;
    
    input[strlen(input)-1] = '\0';
    input++;
    
    if (strlen(input) == 0) return NULL;
    
    char* token = strtok(input, ",");
    if (!token || strcmp(token, "null") == 0) return NULL;
    
    struct TreeNode* root = createNode(atoi(token));
    struct TreeNode* queue[1000];
    int front = 0, rear = 0;
    queue[rear++] = root;
    
    while (front < rear) {
        struct TreeNode* node = queue[front++];
        
        token = strtok(NULL, ",");
        if (token && strcmp(token, "null") != 0) {
            node->left = createNode(atoi(token));
            queue[rear++] = node->left;
        }
        
        token = strtok(NULL, ",");
        if (token && strcmp(token, "null") != 0) {
            node->right = createNode(atoi(token));
            queue[rear++] = node->right;
        }
    }
    
    return root;
}

int main() {
    char input[10000];
    fgets(input, sizeof(input), stdin);
    input[strcspn(input, "\n")] = 0;
    
    struct TreeNode* root = buildTree(input);
    int returnSize;
    int* result = solution(root, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Visit each node exactly once, reverse operation is O(n)

✓ Linear Growth

Space Complexity

O(h)

Stack stores at most h nodes where h is tree height

✓ Linear Space

125.0K Views

Medium Frequency

~15 min Avg. Time

4.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Iterative with Stack — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler