Binary Tree Recursive/Level Traversal

After understanding the Basic Concepts of Binary Trees and Several Special Binary Trees, this article explains how to traverse and access the nodes of a binary tree.

Binary tree traversal algorithms are mainly divided into recursive traversal and level-order traversal, both having code templates. The recursive code template can extend into the DFS algorithm and backtracking algorithm to be discussed later, and the level-order code template can extend into the BFS algorithm. This is why I often emphasize the importance of binary tree structures.

The well-known pre-order, in-order, and post-order traversals all belong to recursive traversal of binary trees, just inserting custom code at different positions of the code template, which I will explain with a visual panel below.

Recursive Traversal (DFS)

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

// 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);
}

// 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);
}

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

// 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 manage to traverse a binary tree? And in what order does it traverse the binary tree?

For a recursive traversal function like traverse, you can think of it as a pointer moving around the binary tree structure. Below is a visual panel to intuitively display the traversal process of this algorithm.

Don't rush; you can review this visual panel several times until you fully understand the traversal order of the traverse function for binary trees.

The traversal order of the traverse function keeps moving towards the left child node until it encounters a null pointer and cannot move further, then tries to move one step towards the right child node; and then continuously tries to move towards the left child node, looping in this manner. If both the left and right subtrees are completed, it returns to the parent node of the previous level.

You can also see from the code that it first recursively calls root.left, then recursively calls root.right. Each time the traverse function is entered, it first recursively traverses the left child node until it encounters a null pointer and cannot move, then it is the turn to move towards the right child node once.

Let's expand this briefly: if we modify the previous traverse function to recursively traverse root.right first and then root.left, what will be the effect?

// 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 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:

// 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);
}

// 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);
}

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

// 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:

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:

// 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
}

// 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
}

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

// 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.

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.

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:

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:

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

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

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)
        }
    }
}

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

Implementation Two

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

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

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

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++
    }
}

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.

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:

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

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

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})
        }
    }
}

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

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.