Preorder Traversal of Binary Trees Recursive Approach

Contents

ProblemExamplesVisualizationSolutionAlgorithmCode

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

Visualization Player

Solution❯

The goal of a preorder traversal is to visit every node in a binary tree in a specific order: root → left → right. When we use recursion, the traversal naturally follows this order because each recursive call takes care of one subtree at a time.

Let’s understand the different scenarios you might encounter:

1. Standard Tree

If the binary tree has both left and right children at multiple levels, we always start by visiting the root node. Then, we go deep into the left subtree recursively. Once the left subtree is fully visited, we move to the right subtree.

2. Skewed Trees

In a left-skewed tree, all nodes only have left children. The recursion keeps going left until it hits a null, and then it backtracks. The order is just a straight path down the left.

In a right-skewed tree, the left recursive calls return immediately (since left children are null), and we end up visiting the root, then the right child, and so on.

3. Single Node

If the tree has only one node (just the root), we simply return that node's value in a list — there are no subtrees to traverse.

4. Empty Tree

If the root node is null, there’s nothing to visit. In this case, we return an empty list [].

Why Recursion Works Well

Recursive traversal is elegant because it handles each subtree independently. The function calls itself on the left child first, then on the right child, and combines results step-by-step as it returns. Each call keeps track of its own position in the tree, so the traversal order is naturally preserved.

In all cases, we follow the same rule: visit node → left → right. This guarantees that we will always get a consistent and correct preorder traversal.

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

Python
Java
JavaScript
C
C++
C#
Kotlin
Swift
Go
Php
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)