Preorder Traversal of Binary Trees Recursive Approach

Binary Trees

Contents

VisualizationProblemExamplesSolutionAlgorithmCode

Visualization Player

Problem Statement❯

Given a binary tree, your task is to perform a preorder traversal using recursion and return the sequence of node values visited.

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

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

If the binary tree is empty, the output should be an empty list [].

Examples❯

Tree Structure Preorder Output Description
[1,2,3,4]
[1, 2, 4, 3] Standard binary tree with left and right children
[1,null,2,null,null,null,3]
[1, 2, 3] Right-skewed tree (no left children)
[1,2,3,4,5]
[1, 2, 4, 5, 3] Full binary tree up to 2 levels
[1]
[1] Single-node tree (root only)
[] [] Empty tree with no nodes

Solution❯

Understanding the Problem

In this problem, we are asked to perform a preorder traversal of a binary tree. This means we want to visit all the nodes in the following specific order: root → left → right.

Binary trees can come in many shapes — balanced, skewed, or even empty — and our goal is to ensure that regardless of the shape, we always return a list of node values in this preorder sequence.

We’ll use a recursive approach that mimics how a human would traverse the tree: start at the root, explore the entire left side, then move to the right side.

Step-by-Step Solution with Example

Step 1: Visualize the Tree

Let's take the example of the following binary tree:


      1
     /     2   3
   /   4   5

The preorder traversal should visit: 1 → 2 → 4 → 5 → 3

Step 2: Understand the Preorder Rule

The rule for preorder traversal is:

  • Visit the root node
  • Recursively do a preorder traversal of the left subtree
  • Recursively do a preorder traversal of the right subtree

Step 3: Write the Recursive Logic

We’ll define a function that:

  • Checks if the current node is null (base case)
  • If not null, adds the node’s value to the result list
  • Recursively calls itself for the left child
  • Then recursively calls itself for the right child

Step 4: Apply the Logic to the Example

Start from root 1:

  • Add 1 to result
  • Go left to 2, add to result
  • Go left to 4, add to result. Left and right are null → backtrack
  • Go right to 5, add to result. Left and right are null → backtrack
  • Back to 1, go right to 3, add to result

Final result: [1, 2, 4, 5, 3]

Edge Cases

Empty Tree

If the tree is empty (i.e., root is null), we return an empty list: []

Single Node Tree

If there is only one node (no left or right child), return a list with just that node's value: [root.val]

Left-Skewed Tree

Each node only has a left child. The result will be a top-to-bottom list from root to the last left node.


    1
   /
  2
 /
3

Traversal: [1, 2, 3]

Right-Skewed Tree

Each node only has a right child. The result will be a top-to-bottom list from root to the last right node.


1
   2
       3

Traversal: [1, 2, 3]

Finally

Preorder traversal is all about visiting nodes in the order: root → left → right. With recursion, this pattern becomes very natural to implement, and it handles all tree structures gracefully.

By breaking the tree into smaller subproblems (left and right subtrees), we simplify the traversal process. Always remember to check for null nodes to handle edge cases smoothly.

This recursive strategy will consistently give us the correct preorder output for any binary tree.

Algorithm Steps❯

  1. Start at the root node of the binary tree.
  2. Visit the current node and process its value.
  3. Recursively traverse the left subtree.
  4. Recursively traverse the right subtree.
  5. If the current node is null, return.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node *left, *right;
} Node;

Node* newNode(int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->left = node->right = NULL;
    return node;
}

void preorder(Node* root) {
    if (root != NULL) {
        printf("%d ", root->data);
        preorder(root->left);
        preorder(root->right);
    }
}

int main() {
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    printf("Preorder traversal: ");
    preorder(root);
    return 0;
}

Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...