Binary Tree Recursive/Level Traversal

labuladongOriginalAbout 4565 words

Prerequisites

Before reading this article, you should first study:

Basic Concepts of Binary Trees and Special Types of Binary Trees

Summary in One Sentence

There are only two ways to traverse a binary tree: recursive traversal and level-order traversal. Recursive traversal can be used to implement DFS algorithms, while level-order traversal can be used to implement BFS algorithms.

The order of visiting nodes in recursive traversal is fixed, but there are three key positions. Inserting code at different positions produces different effects.

The order of visiting nodes in level-order traversal is also fixed, but there are three different coding styles, each suitable for different scenarios.

After understanding the basic concepts of binary trees and special types of binary trees, this article will explain how to traverse and access nodes in a binary tree.

Binary tree traversal algorithms are mainly divided into two types: recursive traversal and level-order traversal. Both have code templates. The recursive template can be extended to DFS and backtracking algorithms, while the level-order template can be extended to BFS algorithms. This is why I often emphasize the importance of binary tree structures.

The commonly known preorder, inorder, and postorder traversals are all types of recursive traversal. The only difference is where you insert your custom code into the template. I will explain this in detail with visual panels.

Recursive Traversal (DFS)

The code template for recursive traversal of a binary tree is as follows:

java

// basic binary tree node
class TreeNode {
    int val;
    TreeNode left, right;
}

// recursive traversal framework for binary tree
void traverse(TreeNode root) {
    if (root == null) {
        return;
    }
    traverse(root.left);
    traverse(root.right);
}

cpp

// basic binary tree node
class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// recursive traversal framework for binary tree
void traverse(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    traverse(root->left);
    traverse(root->right);
}

python

# basic binary tree node
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# recursive traversal framework for binary tree
def traverse(root: TreeNode):
    if root is None:
        return
    traverse(root.left)
    traverse(root.right)

// basic binary tree node
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// recursive traversal framework for binary tree
func traverse(root *TreeNode) {
    if root == nil {
        return
    }
    traverse(root.Left)
    traverse(root.Right)
}

javascript

// basic binary tree node
class TreeNode {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

// recursive traversal framework for binary tree
var traverse = function(root) {
    if (root === null) {
        return;
    }
    traverse(root.left);
    traverse(root.right);
}

Why does this concise code traverse the entire binary tree? In what order does it visit the nodes?

You can think of the traverse recursive function as a pointer moving through the binary tree structure. The following visual panel will show you the traversal process clearly.

Open this visual panel. The position of the root pointer on the right represents where the traverse function is currently visiting. You can click the line console.log("enter" multiple times to observe the order in which the root pointer moves through the tree:

Recursive Traversal of a Binary Tree

Take your time—watch the visual panel as many times as you need until you fully understand the traversal order of the traverse function.

The traversal order of the traverse function is: always go to the left child node first, until you reach a null pointer and cannot go further, then try to go to the right child node; then repeat the process by always going left as far as possible. If both left and right subtrees are finished, return to the parent node.

You can see from the code: the function first recursively calls root.left, then recursively calls root.right. Each time the traverse function is entered, it first traverses to the left child. Only when it cannot go left anymore does it turn to the right child.

Now, let's try a simple change: if we modify the traverse function to recursively traverse root.right before root.left, what will happen?

// modify the standard binary tree traversal framework
void traverseFlip(TreeNode root) {
    if (root == null) {
        return;
    }
    // traverse the right subtree first, then traverse the left subtree
    traverseFlip(root.right);
    traverseFlip(root.left);
}

You can first visualize the order in which this function traverses binary tree nodes, then open the visualization panel below, and click multiple times on the line if (root === null). Observe the order in which the root pointer moves through the tree and see if it matches your expectations:

Algorithm Visualization

You can see that the traverseFlip function also traverses all nodes in the binary tree, but in the opposite order to the standard traverse function.

I provide this traverseFlip example to illustrate that:

The order of recursive node traversal (i.e., the order in which root moves through the tree in the visualization panel) depends solely on the order of recursive calls to the left and right child nodes, and is unrelated to other code.

When we refer to binary tree traversal, we typically do not traverse the tree like traverseFlip. The default is to traverse from left to right, so when we refer to the code template for binary tree traversal, it means traversal from left to right:

java

// basic binary tree node
class TreeNode {
    int val;
    TreeNode left, right;
}

// recursive traversal framework for binary tree
void traverse(TreeNode root) {
    if (root == null) {
        return;
    }
    traverse(root.left);
    traverse(root.right);
}

cpp

// basic binary tree node
class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// recursive traversal framework for binary tree
void traverse(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    traverse(root->left);
    traverse(root->right);
}

python

# basic binary tree node
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# recursive traversal framework for binary tree
def traverse(root: TreeNode):
    if root is None:
        return
    traverse(root.left)
    traverse(root.right)

// basic binary tree node
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// recursive traversal framework for binary tree
func traverse(root *TreeNode) {
    if root == nil {
        return
    }
    traverse(root.Left)
    traverse(root.Right)
}

javascript

// basic binary tree node
class TreeNode {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

// recursive traversal framework for binary tree
var traverse = function(root) {
    if (root === null) {
        return;
    }
    traverse(root.left);
    traverse(root.right);
}

As long as this left-to-right call order remains unchanged, the order in which the traverse function accesses nodes is fixed. You can insert ten thousand lines of code, and it will not change.

Some readers with a basic understanding of data structures may be confused:

That's not right. Anyone who has taken a college course in data structures knows that binary trees have pre-order, in-order, and post-order traversals, which result in three different sequences. Why do you say that the recursive node traversal order is fixed here?

This is a good question. Let's address it below.

Understanding Pre-order, In-order, and Post-order Traversal

The order of recursive traversal, that is, the order in which the traverse function accesses nodes, is indeed fixed. As shown in the visualization panel, the order in which the root pointer moves through the tree is fixed:

Algorithm Visualization

However, the effect can differ depending on where you write code within the traverse function. The different results of pre-order, in-order, and post-order traversals occur because you write code in different locations, producing different outcomes.

For example, when you first enter a node, you know nothing about its child nodes, while when you are about to leave a node, you have traversed all its child nodes. Writing code in these two situations can certainly yield different effects.

The so-called pre-order, in-order, and post-order traversal essentially involves writing code in different places within the binary tree traversal framework:

java

// Binary tree traversal framework
void traverse(TreeNode root) {
    if (root == null) {
        return;
    }
    // pre-order position
    traverse(root.left);
    // in-order position
    traverse(root.right);
    // post-order position
}

cpp

// binary tree traversal framework
void traverse(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    // pre-order position
    traverse(root->left);
    // in-order position
    traverse(root->right);
    // post-order position
}

python

# Binary tree traversal framework
def traverse(root):
    if root is None:
        return
    # Pre-order position
    traverse(root.left)
    # In-order position
    traverse(root.right)
    # Post-order position

// Binary tree traversal framework
func traverse(root *TreeNode) {
    if root == nil {
        return
    }
    // Preorder position
    traverse(root.Left)
    // Inorder position
    traverse(root.Right)
    // Postorder position
}

javascript

// binary tree traversal framework
var traverse = function(root) {
    if (root === null) {
        return;
    }
    // pre-order position
    traverse(root.left);
    // in-order position
    traverse(root.right);
    // post-order position
};

The code at the preorder position is executed immediately upon entering a node; the code at the inorder position is executed after traversing the left subtree and before traversing the right subtree; the code at the postorder position is executed after traversing both the left and right subtrees:

The visual code below will help you understand this intuitively.

Please open the visual panel below and click multiple times on the line of code if (root == null). You will see that the order in which the root pointer moves on the tree is consistent with what was described; the order in which nodes turn green represents the result of the preorder traversal, because the code at the preorder position is executed as soon as the node is entered. Thus, the preorder traversal follows the path of the root pointer:

Preorder Traversal of a Binary Tree

The code at the inorder position is executed after the left subtree has been traversed and before the right subtree is traversed. Please open the visual panel below and click multiple times on the line of code if (root == null). You will see that the order in which the root pointer moves on the tree is consistent with what was described; the order in which nodes turn blue represents the result of the inorder traversal. You will notice that a node turns blue only after its left subtree has been traversed:

Inorder Traversal of a Binary Tree

The code at the postorder position is executed when both the left and right subtrees have been traversed and the node is about to be exited. Please open the visual panel below and click multiple times on the line of code if (root == null). You will see that the order in which the root pointer moves on the tree is consistent with what was described; the order in which nodes turn red represents the result of the postorder traversal. You will notice that a node turns red only after both its left and right subtrees have been traversed:

Postorder Traversal of a Binary Tree

Understanding the preorder, inorder, and postorder positions is crucial. Carefully study the visual panels above to mentally compute the traversal results for any binary tree.

Key Point

It is particularly emphasized that the key difference among the three positions lies in the timing of execution.

In real algorithm problems, you won't simply be asked to compute the traversal results of preorder, inorder, or postorder. Instead, you need to place the correct code in the correct position, so you must accurately understand the different effects produced by the code at each position to write precise code.

I will further explore the preorder, inorder, and postorder positions in the binary tree traversal framework and how to apply them to backtracking and dynamic programming algorithms in Binary Tree Algorithm Concepts (Guide) and exercises.

The final point of knowledge: the result of the inorder traversal of a Binary Search Tree (BST) is ordered, which is an important property of BSTs.

You can view this in the visual panel. Click on the line of code res.push(root.val);, and you will see the order in which nodes are accessed during the inorder traversal:

Inorder Traversal of a BST is Ordered

In the subsequent BST-related exercise set, some problems will utilize this property.

Level Order Traversal (BFS)

The recursive traversal mentioned above relies on the function stack to recursively traverse the binary tree, starting from the far left and moving column by column to the far right.

Level order traversal of a binary tree, as the name implies, traverses the tree level by level:

Level order traversal requires the use of a queue, and depending on different needs, there can be three different implementations, which are listed below.

Implementation One

This is the simplest implementation, with the code as follows:

java

void levelOrderTraverse(TreeNode root) {
    if (root == null) {
        return;
    }
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    while (!q.isEmpty()) {
        TreeNode cur = q.poll();
        // visit the cur node
        System.out.println(cur.val);

        // add the left and right children of cur to the queue
        if (cur.left != null) {
            q.offer(cur.left);
        }
        if (cur.right != null) {
            q.offer(cur.right);
        }
    }
}

cpp

void levelOrderTraverse(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    std::queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* cur = q.front();
        q.pop();
        // visit the cur node
        std::cout << cur->val << std::endl;
        
        // add the left and right children of cur to the queue
        if (cur->left != nullptr) {
            q.push(cur->left);
        }
        if (cur->right != nullptr) {
            q.push(cur->right);
        }
    }
}

python

from collections import deque

def levelOrderTraverse(root):
    if root is None:
        return
    q = deque()
    q.append(root)
    while q:
        cur = q.popleft()
        # visit cur node
        print(cur.val)

        # add cur's left and right children to the queue
        if cur.left is not None:
            q.append(cur.left)
        if cur.right is not None:
            q.append(cur.right)

func levelOrderTraverse(root *TreeNode) {
    if root == nil {
        return
    }
    q := []*TreeNode{}
    q = append(q, root)
    for len(q) > 0 {
        cur := q[0]
        q = q[1:]
        // visit cur node
        fmt.Println(cur.Val)
        
        // add cur's left and right children to the queue
        if cur.Left != nil {
            q = append(q, cur.Left)
        }
        if cur.Right != nil {
            q = append(q, cur.Right)
        }
    }
}

javascript

var levelOrderTraverse = function(root) {
    if (root === null) {
        return;
    }
    var q = [];
    q.push(root);
    while (q.length !== 0) {
        var cur = q.shift();
        // visit cur node
        console.log(cur.val);

        // add cur's left and right children to the queue
        if (cur.left !== null) {
            q.push(cur.left);
        }
        if (cur.right !== null) {
            q.push(cur.right);
        }
    }
}

You can open this visualization panel, click on the line of code while (q.length > 0), and observe the order in which the cur variable moves through the tree. You will see that level order traversal visits the tree nodes level by level, from left to right:

Level Order Traversal of a Binary Tree

Advantages and Disadvantages of This Implementation

The biggest advantage of this implementation is its simplicity. Each time, you take the front element of the queue and add its left and right child nodes to the queue, and that's it.

However, the disadvantage of this implementation is that it cannot determine which level the current node is on. Knowing the level of a node is a common requirement, for example, collecting nodes at each level or calculating the minimum depth of a binary tree.

Therefore, although this implementation is simple, it is not used often. The implementation described below is more common.

Implementation Two

By slightly modifying the above solution, we arrive at the following implementation:

java

void levelOrderTraverse(TreeNode root) {
    if (root == null) {
        return;
    }
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    // record the current level being traversed (root node is considered as level 1)
    int depth = 1;

    while (!q.isEmpty()) {
        int sz = q.size();
        for (int i = 0; i < sz; i++) {
            TreeNode cur = q.poll();
            // visit the cur node and know its level
            System.out.println("depth = " + depth + ", val = " + cur.val);

            // add the left and right children of cur to the queue
            if (cur.left != null) {
                q.offer(cur.left);
            }
            if (cur.right != null) {
                q.offer(cur.right);
            }
        }
        depth++;
    }
}

cpp

void levelOrderTraverse(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    queue<TreeNode*> q;
    q.push(root);
    // record the current level being traversed (the root node is considered as level 1)
    int depth = 1;

    while (!q.empty()) {
        int sz = q.size();
        for (int i = 0; i < sz; i++) {
            TreeNode* cur = q.front();
            q.pop();
            // visit the cur node, knowing its level
            cout << "depth = " << depth << ", val = " << cur->val << endl;

            // add the left and right children of cur to the queue
            if (cur->left != nullptr) {
                q.push(cur->left);
            }
            if (cur->right != nullptr) {
                q.push(cur->right);
            }
        }
        depth++;
    }
}

python

from collections import deque

def levelOrderTraverse(root):
    if root is None:
        return
    q = deque()
    q.append(root)
    # record the current depth being traversed (root node is considered as level 1)
    depth = 1

    while q:
        sz = len(q)
        for i in range(sz):
            cur = q.popleft()
            # visit cur node and know its depth
            print(f"depth = {depth}, val = {cur.val}")

            # add cur's left and right children to the queue
            if cur.left is not None:
                q.append(cur.left)
            if cur.right is not None:
                q.append(cur.right)
        depth += 1

func levelOrderTraverse(root *TreeNode) {
    if root == nil {
        return
    }
    q := []*TreeNode{root}
    // record the current depth being traversed (root node is considered as level 1)
    depth := 1

    for len(q) > 0 {
        // get the current queue length
        sz := len(q)
        for i := 0; i < sz; i++ {
            // dequeue the front of the queue
            cur := q[0]
            q = q[1:]
            // visit the cur node and know its depth
            fmt.Printf("depth = %d, val = %d\n", depth, cur.Val)

            // add cur's left and right children to the queue
            if cur.Left != nil {
                q = append(q, cur.Left)
            }
            if cur.Right != nil {
                q = append(q, cur.Right)
            }
        }
        depth++
    }
}

javascript

var levelOrderTraverse = function(root) {
    if (root === null) {
        return;
    }
    let q = [];
    q.push(root);
    // record the current depth (root node is considered as level 1)
    let depth = 1;

    while (q.length !== 0) {
        let sz = q.length;
        for (let i = 0; i < sz; i++) {
            let cur = q.shift();
            // visit the cur node and know its depth
            console.log("depth = " + depth + ", val = " + cur.val);

            // add the left and right children of cur to the queue
            if (cur.left !== null) {
                q.push(cur.left);
            }
            if (cur.right !== null) {
                q.push(cur.right);
            }
        }
        depth++;
    }
};

Notice the inner for loop in the code:

int sz = q.size();
for (int i = 0; i < sz; i++) {
    ...
}

The variable i keeps track of which number cur is in the current level. In most algorithm problems, this variable is not necessary, so you can use the following approach instead:

int sz = q.size();
while (sz-- > 0) {
    ...
}

This is a matter of preference, so choose whichever you like.

However, make sure to save the queue length sz before the loop starts because the length of the queue will change during the loop, and you cannot use q.size() directly as the loop condition.

You can open this visual panel and click on the line with console.log to observe the order in which the cur variable traverses the tree. You will see that it is still level by level, from left to right, exploring the binary tree nodes, but this time it will also output the level of each node:

Level Order Traversal of a Binary Tree 2

This approach allows you to record the level of each node, which can solve problems like finding the minimum depth of a binary tree. It is our most commonly used level order traversal method.

Method Three

If method two is the most common, why is there a method three? Because it lays the groundwork for more advanced topics.

Right now, we are just discussing level order traversal of a binary tree, but level order traversal can be extended to level order traversal of an N-ary tree, BFS traversal of a graph, and the classic BFS brute-force algorithm framework. Therefore, we need to expand a bit here.

In method two, every time we traverse down a level, we increment depth by 1, which can be understood as each tree branch having a weight of 1. The depth of each node in a binary tree is the sum of the path weights from the root node to that node, and all nodes on the same level have the same path weight sum.

Now suppose if the path weight sum of each branch can be any value, and you are asked to perform a level order traversal of the entire tree and print the path weight sum of each node, how would you do it?

In such a case, the path weight sums of nodes on the same level might not be the same, and maintaining just one depth variable, as in method two, would not suffice.

Method three addresses this issue by adding a State class based on method one, allowing each node to maintain its own path weight sum. The code is as follows:

java

class State {
    TreeNode node;
    int depth;

    State(TreeNode node, int depth) {
        this.node = node;
        this.depth = depth;
    }
}

void levelOrderTraverse(TreeNode root) {
    if (root == null) {
        return;
    }
    Queue<State> q = new LinkedList<>();
    // the path weight sum of the root node is 1
    q.offer(new State(root, 1));

    while (!q.isEmpty()) {
        State cur = q.poll();
        // visit the cur node, while knowing its path weight sum
        System.out.println("depth = " + cur.depth + ", val = " + cur.node.val);

        // add the left and right child nodes of cur to the queue
        if (cur.node.left != null) {
            q.offer(new State(cur.node.left, cur.depth + 1));
        }
        if (cur.node.right != null) {
            q.offer(new State(cur.node.right, cur.depth + 1));
        }
    }
}

cpp

class State {
public:
    TreeNode* node;
    int depth;

    State(TreeNode* node, int depth) : node(node), depth(depth) {}
};

void levelOrderTraverse(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    queue<State> q;
    // the path weight sum of the root node is 1
    q.push(State(root, 1));

    while (!q.empty()) {
        State cur = q.front();
        q.pop();
        // visit the cur node, while knowing its path weight sum
        cout << "depth = " << cur.depth << ", val = " << cur.node->val << endl;

        // add the left and right children of cur to the queue
        if (cur.node->left != nullptr) {
            q.push(State(cur.node->left, cur.depth + 1));
        }
        if (cur.node->right != nullptr) {
            q.push(State(cur.node->right, cur.depth + 1));
        }
    }
}

python

class State:
    def __init__(self, node, depth):
        self.node = node
        self.depth = depth

def levelOrderTraverse(root):
    if root is None:
        return
    q = deque()
    # the path weight sum of the root node is 1
    q.append(State(root, 1))

    while q:
        cur = q.popleft()
        # visit the cur node, and know its path weight sum
        print(f"depth = {cur.depth}, val = {cur.node.val}")

        # add the left and right child nodes of cur to the queue
        if cur.node.left is not None:
            q.append(State(cur.node.left, cur.depth + 1))
        if cur.node.right is not None:
            q.append(State(cur.node.right, cur.depth + 1))

type State struct {
    node  *TreeNode
    depth int
}

func levelOrderTraverse(root *TreeNode) {
    if root == nil {
        return
    }
    q := []State{{root, 1}}

    for len(q) > 0 {
        cur := q[0]
        q = q[1:]
        // visit the cur node, also know its path weight sum
        fmt.Printf("depth = %d, val = %d\n", cur.depth, cur.node.Val)

        // add cur's left and right children to the queue
        if cur.node.Left != nil {
            q = append(q, State{cur.node.Left, cur.depth + 1})
        }
        if cur.node.Right != nil {
            q = append(q, State{cur.node.Right, cur.depth + 1})
        }
    }
}

javascript

function State(node, depth) {
    this.node = node;
    this.depth = depth;
}

var levelOrderTraverse = function(root) {
    if (root === null) {
        return;
    }
    // @visualize bfs
    var q = [];
    // the path weight sum of the root node is 1
    q.push(new State(root, 1));

    while (q.length !== 0) {
        var cur = q.shift();
        // visit the cur node, while knowing its path weight sum
        console.log("depth = " + cur.depth + ", val = " + cur.node.val);

        // add the left and right children of cur to the queue
        if (cur.node.left !== null) {
            q.push(new State(cur.node.left, cur.depth + 1));
        }
        if (cur.node.right !== null) {
            q.push(new State(cur.node.right, cur.depth + 1));
        }
    }
};

You can open this visualization panel and click on the line of code with console.log. You will see the nodes of the binary tree being traversed level by level from left to right, and the level of each node will be output:

Binary Tree Level Order Traversal 3

In this way, each node has its own depth variable, which is the most flexible and meets the needs of all BFS algorithms. However, since defining an extra State class can be cumbersome, using the second approach is sufficient when unnecessary.

You'll soon learn that scenarios with weighted edges belong to graph structure algorithms. This approach will be used in the upcoming BFS Algorithm Exercise Set and Dijkstra's Algorithm.

Other Traversals?

There are only two types of binary tree traversals mentioned above. There might be other variations, but they are merely differences in presentation. Fundamentally, they cannot deviate from these two traversal methods.

For instance, you might see code that uses a stack to iteratively traverse a binary tree. However, this is essentially still a recursive traversal, with the stack manually maintaining the recursion calls.

Similarly, you might see code that recursively traverses a binary tree level by level. This is essentially level-order traversal, but it presents the for loop in level-order traversal code in a recursive form.

In summary, do not be misled by appearances. There are only these two traversal methods for binary trees. By mastering these two approaches through the following tutorials and exercises, brute-force algorithms will be a breeze.