Binary Tree Preorder Traversal - Practice Coding Problems

Binary Tree Preorder Traversal - Problem

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

In preorder traversal, we visit nodes in the following order:

Root node first
Left subtree
Right subtree

For example, given a tree with root 1, left child 2, and right child 3, the preorder traversal would be [1, 2, 3].

Input & Output

Example 1 — Basic Tree

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

› Output: [1,2,3]

💡 Note: Visit root 1 first, then right subtree. In right subtree: visit 2, then its left child 3. Final order: 1 → 2 → 3

Example 2 — Empty Tree

$ Input: root = []

› Output: []

💡 Note: Empty tree has no nodes, so preorder traversal returns empty array

Example 3 — Single Node

$ Input: root = [1]

› Output: [1]

💡 Note: Tree with only root node returns array with just that value

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 containing integer values

Preorder Visit

Visit root first, then left subtree, then right subtree

Output Array

Array of values in preorder sequence

Key Takeaway

🎯 Key Insight: Preorder means process current node before exploring children

Asked in

G Google 45 a Amazon 38 M Microsoft 32 A Apple 28

The key insight is that preorder traversal visits root before children. Recursive approach naturally follows this pattern: visit current node, then left, then right. Iterative approach uses a stack, pushing right child before left (since stack is LIFO). Best approach depends on preference: recursion is cleaner but uses call stack. Time: O(n), Space: O(h)

Common Approaches

Approach	Time	Space	Notes
✓ Recursive DFS	O(n)	O(h)	Use recursion to traverse root → left → right
Iterative Stack	O(n)	O(h)	Use explicit stack to simulate recursion

Recursive DFS — Algorithm Steps

Visit current node and add to result
Recursively traverse left subtree
Recursively traverse right subtree

Visualization

Tap to expand

Step-by-Step Walkthrough

Visit Root

Process current node first

Traverse Left

Recursively visit left subtree

Traverse Right

Recursively visit 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 dfs(struct TreeNode* node, int* result, int* size) {
    if (!node) return;
    result[(*size)++] = node->val;
    dfs(node->left, result, size);
    dfs(node->right, result, size);
}

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

int main() {
    // For simplicity, create a sample tree for demonstration
    struct TreeNode* root = createNode(1);
    root->right = createNode(2);
    root->right->left = createNode(3);
    
    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

✓ Linear Growth

Space Complexity

O(h)

Recursion stack depth equals tree height h

✓ Linear Space

89.2K Views

High Frequency

~15 min Avg. Time

2.8K 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 DFS — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler