Binary Tree Inorder Traversal - Practice Coding Problems

Binary Tree Inorder Traversal - Problem

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

In an inorder traversal, we visit the nodes in the following order:

Traverse the left subtree
Visit the root node
Traverse the right subtree

For example, given the tree [1,null,2,3], the inorder traversal would be [1,3,2].

Input & Output

Example 1 — Simple Tree

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

› Output: [1,3,2]

💡 Note: Inorder traversal: no left child of 1, visit 1, then go right to 2. For node 2: visit left child 3 first, then visit 2, no right child. Result: [1,3,2]

Example 2 — Empty Tree

$ Input: root = []

› Output: []

💡 Note: Empty tree has no nodes to traverse, so return empty array

Example 3 — Single Node

$ Input: root = [1]

› Output: [1]

💡 Note: Single node tree: no left child, visit root 1, no right child. Result: [1]

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 represented as array [1,null,2,3]

Traverse Inorder

Visit left subtree, root, then right subtree

Output Array

Collect node values in traversal order

Key Takeaway

🎯 Key Insight: Inorder traversal naturally produces sorted order for binary search trees

Asked in

f Facebook 52 M Microsoft 38 a Amazon 31 G Google 28

Binary tree inorder traversal visits nodes in left → root → right order. The recursive approach is most intuitive, while the iterative stack approach avoids potential stack overflow. Both have O(n) time and O(h) space complexity. Best approach depends on tree depth constraints.

Common Approaches

Approach	Time	Space	Notes
✓ Recursive Approach	O(n)	O(h)	Use recursion to traverse left, visit root, then traverse right
Iterative Stack Approach	O(n)	O(h)	Use an explicit stack to simulate recursion iteratively

Recursive Approach — Algorithm Steps

Base case: if node is null, return
Recursively traverse left subtree
Add current node value to result
Recursively traverse right subtree

Visualization

Tap to expand

Step-by-Step Walkthrough

Start at Root

Begin traversal at root node

Go Left First

Recursively traverse entire left subtree

Visit Root

Add current node value to result

Go Right

Recursively traverse right subtree

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 = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

void inorder(struct TreeNode* node, int* result, int* index) {
    if (!node) return;
    inorder(node->left, result, index);
    result[(*index)++] = node->val;
    inorder(node->right, result, index);
}

int* solution(struct TreeNode* root, int* returnSize) {
    int* result = (int*)malloc(1000 * sizeof(int));
    *returnSize = 0;
    inorder(root, result, returnSize);
    return result;
}

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

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    struct TreeNode* root = buildTree(line);
    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)

We visit each node exactly once in the tree

✓ Linear Growth

Space Complexity

O(h)

Recursion stack depth equals tree height h, plus O(n) for result array

✓ Linear Space

892.0K Views

High Frequency

~15 min Avg. Time

11.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

Recursive Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler