Preorder Traversal of a Binary Tree using Recursion

Problem and examples

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 [].

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

Explore Preorder Traversal of Binary Trees - Recursive

Load an example or enter your own input. Use the player controls to follow each change.

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.

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.

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

Implementation and efficiency

C implementation

#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;
}

C++ implementation

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(NULL), right(NULL) {}
};

void preorder(Node* root) {
    if (root != nullptr) {
        cout << root->data << " ";
        preorder(root->left);
        preorder(root->right);
    }
}

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

Python implementation

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def preorder(root):
    if root:
        print(root.data, end=' ')
        preorder(root.left)
        preorder(root.right)

# Example usage
if __name__ == '__main__':
    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left.left = Node(4)
    root.left.right = Node(5)
    print('Preorder traversal:')
    preorder(root)

Java implementation

class Node {
    int data;
    Node left, right;
    Node(int data) {
        this.data = data;
        left = right = null;
    }
}

public class PreorderTraversal {
    public static void preorder(Node root) {
        if (root == null) return;
        System.out.print(root.data + " ");
        preorder(root.left);
        preorder(root.right);
    }
    
    public static void main(String[] args) {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        System.out.println("Preorder traversal:");
        preorder(root);
    }
}

JavaScript implementation

class Node {
    constructor(data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

function preorder(root) {
    if (root) {
        process.stdout.write(root.data + ' ');
        preorder(root.left);
        preorder(root.right);
    }
}

// Example usage:
const root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
console.log('Preorder traversal:');
preorder(root);

Go implementation

package main

import "fmt"

type Node struct {
    data int
    left, right *Node
}

func newNode(data int) *Node {
    return &Node{data: data}
}

func preorder(root *Node) {
    if root != nil {
        fmt.Printf("%d ", root.data)
        preorder(root.left)
        preorder(root.right)
    }
}

func main() {
    root := newNode(1)
    root.left = newNode(2)
    root.right = newNode(3)
    root.left.left = newNode(4)
    root.left.right = newNode(5)
    fmt.Print("Preorder traversal: ")
    preorder(root)
}

Rust implementation

struct Node {
    data: i32,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>
}

impl Node {
    fn new(data: i32) -> Self {
        Node { data, left: None, right: None }
    }
}

fn preorder(node: &Option<Box<Node>>) {
    if let Some(n) = node {
        print!("{} ", n.data);
        preorder(&n.left);
        preorder(&n.right);
    }
}

fn main() {
    let mut root = Box::new(Node::new(1));
    root.left = Some(Box::new(Node::new(2)));
    root.right = Some(Box::new(Node::new(3)));
    root.left.as_mut().unwrap().left = Some(Box::new(Node::new(4)));
    root.left.as_mut().unwrap().right = Some(Box::new(Node::new(5)));
    println!("Preorder traversal:");
    preorder(&Some(root));
}

Kotlin implementation

class Node(val data: Int) {
    var left: Node? = null
    var right: Node? = null
}

fun preorder(root: Node?) {
    if (root != null) {
        print("${root.data} ")
        preorder(root.left)
        preorder(root.right)
    }
}

fun main() {
    val root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left?.left = Node(4)
    root.left?.right = Node(5)
    println("Preorder traversal:")
    preorder(root)
}

Swift implementation

class Node {
    var data: Int
    var left: Node?
    var right: Node?
    init(_ data: Int) {
        self.data = data
    }
}

func preorder(_ root: Node?) {
    if let root = root {
        print(root.data, terminator: " ")
        preorder(root.left)
        preorder(root.right)
    }
}

let root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left?.left = Node(4)
root.left?.right = Node(5)
print("Preorder traversal:", terminator: " ")
preorder(root)

TypeScript implementation

class Node {
    data: number;
    left: Node | null = null;
    right: Node | null = null;
    constructor(data: number) {
        this.data = data;
    }
}

function preorder(root: Node | null): void {
    if (root) {
        process.stdout.write(root.data + ' ');
        preorder(root.left);
        preorder(root.right);
    }
}

const root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
console.log('Preorder traversal:');
preorder(root);