Binary Tree Recursive/Level Traversal

After understanding the Basic Concepts of Binary Trees and Some Special Types of Binary Trees, this article will explain how to traverse and access the nodes of a binary tree.

Recursive Traversal (DFS)

Framework for binary tree traversal:

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

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

// binary tree traversal framework
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

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

// binary tree traversal framework
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;
    }
}

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

Why can this concise code traverse a binary tree? In what order does it traverse the tree?

For a recursive traversal function like traverse, you can think of it as a pointer moving around the structure of the binary tree. I'll use a visualization to intuitively show you how this function traverses the tree.

By exploring this visualization panel, the position of the root pointer on the right indicates the currently visited node, which is the current position of the traverse function. The orange section displays the call stack of the traverse function. You can click the play button in the upper left corner to observe the changes in the root pointer's position:

The traversal order of the traverse function is to move left continuously until it encounters a null pointer and cannot move further, then it attempts to move right once; it repeats the process of moving left continuously. If both left and right subtrees are fully traversed, it returns to the parent node. This is evident from the code where root.left is called recursively before root.right.

The order of this recursive traversal is fixed, and it's crucial to remember it; otherwise, you will struggle with binary tree structures.

Readers with a basic understanding of data structures might ask: Isn't it true that binary trees have pre-order, in-order, and post-order traversals, resulting in three different orders? Why do you say the order of recursive traversal is fixed here?

This is a great question, and I'll explain.

For example, when you first enter a node, you are unaware of its child nodes, but when you leave a node, all its child nodes have been traversed. Writing code in these two scenarios can yield different effects.

The so-called pre-order, in-order, and post-order traversals are just writing code at different positions 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 pre-order position is executed when entering a node; the code at the in-order position is executed after the left subtree is traversed but before the right subtree is traversed; the code at the post-order position is executed after both left and right subtrees have been traversed:

The pre-order, in-order, and post-order positions of a binary tree are crucial. I will explore the differences and connections of these traversals and how to apply them in backtracking and dynamic programming algorithms in Binary Tree Algorithm Guide and exercises. We won't delve into details here.

Some readers might wonder why the traverse function first recursively traverses root.left and then root.right. Can it be reversed?

Certainly, it can be reversed, but the conventional pre-order, in-order, and post-order traversals assume left before right. This is a customary convention. If you insist on doing right before left, your traversals will differ from the common understanding, which could increase communication costs unnecessarily. Therefore, unless a problem specifically requires it, it is advisable to follow the left before right sequence.

Level Order Traversal (BFS)

The recursive traversal mentioned above relies on the function stack to recursively traverse the binary tree. If you consider the recursive function traverse as a pointer, this pointer moves across the binary tree generally starting from the far left and moving column by column to the far right.

Level order traversal of a binary tree, as the name suggests, involves traversing the binary tree level by level. This traversal method requires the use of a queue to implement, and depending on different needs, there are mainly three different approaches. Below, we will list them one by one.

Approach One

This is the simplest approach, and the code is 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);
        }
    }
}

Method Two

With slight modifications to the above solution, we arrive at the following approach:

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;
    }
    var q = [];
    q.push(root);
    // record the current depth (root node is considered as level 1)
    var depth = 1;

    while (q.length !== 0) {
        var sz = q.length;
        for (var i = 0; i < sz; i++) {
            var 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.

Why BFS is Often Used to Find the Shortest Path

By using a visual panel along with an example problem, you'll understand immediately.

Consider LeetCode Problem 111, "Minimum Depth of Binary Tree":

111. Minimum Depth of Binary Tree | LeetCode |

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Note: A leaf is a node with no children.

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: 2

Example 2:

Input: root = [2,null,3,null,4,null,5,null,6]
Output: 5

Constraints:

• The number of nodes in the tree is in the range [0, 105].
• -1000 <= Node.val <= 1000

The minimum depth of a binary tree is the "distance from the root node to the nearest leaf node," so essentially, this problem is about finding the shortest distance.

Both DFS recursive traversal and BFS level-order traversal can solve this problem. Let's first look at the DFS recursive traversal solution:

class Solution {
    // record the minimum depth (the distance from the root to the nearest leaf node)
    private int minDepth = Integer.MAX_VALUE;
    // record the depth of the current node being traversed
    private int currentDepth = 0;

    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // start DFS traversal from the root node
        traverse(root);
        return minDepth;
    }

    private void traverse(TreeNode root) {
        if (root == null) {
            return;
        }

        // increase the current depth when entering a node in the preorder position
        currentDepth++;

        // if the current node is a leaf, update the minimum depth
        if (root.left == null && root.right == null) {
            minDepth = Math.min(minDepth, currentDepth);
        }

        traverse(root.left);
        traverse(root.right);

        // decrease the current depth when leaving a node in the postorder position
        currentDepth--;
    }
}

class Solution {
private:
    // record the minimum depth (the distance from the root to the nearest leaf node)
    int minDepthValue = INT_MAX;
    // record the depth of the current node being traversed
    int currentDepth = 0;

public:
    int minDepth(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }

        // start DFS traversal from the root node
        traverse(root);
        return minDepthValue;
    }

    void traverse(TreeNode* root) {
        if (root == nullptr) {
            return;
        }

        // increase the current depth when entering a node in the preorder position
        currentDepth++;

        // if the current node is a leaf, update the minimum depth
        if (root->left == nullptr && root->right == nullptr) {
            minDepthValue = min(minDepthValue, currentDepth);
        }

        traverse(root->left);
        traverse(root->right);

        // decrease the current depth when leaving a node in the postorder position
        currentDepth--;
    }
};

class Solution:
    def __init__(self):
        # record the minimum depth (the distance from the root to the nearest leaf node)
        self.minDepthValue = float('inf')
        # record the depth of the current node being traversed
        self.currentDepth = 0

    def minDepth(self, root: TreeNode) -> int:
        if root is None:
            return 0

        # start DFS traversal from the root node
        self.traverse(root)
        return self.minDepthValue

    def traverse(self, root: TreeNode) -> None:
        if root is None:
            return

        # increase the current depth when entering a node in the preorder position
        self.currentDepth += 1

        # if the current node is a leaf, update the minimum depth
        if root.left is None and root.right is None:
            self.minDepthValue = min(self.minDepthValue, self.currentDepth)

        self.traverse(root.left)
        self.traverse(root.right)

        # decrease the current depth when leaving a node in the postorder position
        self.currentDepth -= 1

func minDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }

    // record the minimum depth (the distance from the root to the nearest leaf node)
    minDepthValue := math.MaxInt32
    // record the depth of the current node being traversed
    currentDepth := 0

    var traverse func(*TreeNode)
    traverse = func(root *TreeNode) {
        if root == nil {
            return
        }

        // increase the current depth when entering a node in the preorder position
        currentDepth++

        // if the current node is a leaf, update the minimum depth
        if root.Left == nil && root.Right == nil {
            minDepthValue = min(minDepthValue, currentDepth)
        }

        traverse(root.Left)
        traverse(root.Right)

        // decrease the current depth when leaving a node in the postorder position
        currentDepth--
    }

    // start DFS traversal from the root node
    traverse(root)
    return minDepthValue
}

var minDepth = function(root) {
    if (root === null) {
        return 0;
    }
    
    // record the minimum depth (the distance from the root to the nearest leaf node)
    let minDepthValue = Infinity;

    // record the depth of the current node being traversed
    let currentDepth = 0;

    const traverse = function(root) {
        if (root === null) {
            return;
        }

        // increase the current depth when entering a node in the preorder position
        currentDepth++;

        // if the current node is a leaf, update the minimum depth
        if (root.left === null && root.right === null) {
            minDepthValue = Math.min(minDepthValue, currentDepth);
        }

        traverse(root.left);
        traverse(root.right);

        // decrease the current depth when leaving a node in the postorder position
        currentDepth--;
    };

    // start DFS traversal from the root node
    traverse(root);
    return minDepthValue;
};

Whenever a leaf node of a branch is reached, the minimum depth is updated. After the entire tree is traversed, the minimum depth of the tree can be determined.

Can you end the algorithm early without traversing the entire tree? No, you must know the depth of each branch (the distance from the root node to a leaf node) to find the smallest one.

Now let's look at the BFS level-order traversal solution. Due to the characteristic of BFS traversing a binary tree level by level from top to bottom, the minimum depth can be determined once the first leaf node is reached:

class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        // the root itself is one layer, initialize depth to 1
        int depth = 1;

        while (!q.isEmpty()) {

            int sz = q.size();
            // traverse the nodes of the current layer
            for (int i = 0; i < sz; i++) {
                TreeNode cur = q.poll();
                // check if we have reached a leaf node
                if (cur.left == null && cur.right == null)
                    return depth;
                // add the nodes of the next layer to the queue
                if (cur.left != null)
                    q.offer(cur.left);
                if (cur.right != null)
                    q.offer(cur.right);
            }
            // increment the depth here
            depth++;
        }
        return depth;
    }
}

class Solution {
public:
    int minDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        queue<TreeNode*> q;
        q.push(root);
        // the root itself is one layer, initialize depth to 1
        int depth = 1;

        while (!q.empty()) {
            int sz = q.size();
            // traverse the nodes of the current layer
            for (int i = 0; i < sz; i++) {
                TreeNode* cur = q.front();
                q.pop();
                // check if we have reached a leaf node
                if (cur->left == nullptr && cur->right == nullptr)
                    return depth;
                // add the nodes of the next layer to the queue
                if (cur->left != nullptr)
                    q.push(cur->left);
                if (cur->right != nullptr)
                    q.push(cur->right);
            }
            // increment the depth here
            depth++;
        }
        return depth;
    }
};

class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if root is None:
            return 0
        q = deque([root])
        # the root itself is one layer, initialize depth to 1
        depth = 1

        while q:
            sz = len(q)
            # traverse the nodes of the current layer
            for _ in range(sz):
                cur = q.popleft()
                # check if we have reached a leaf node
                if cur.left is None and cur.right is None:
                    return depth
                # add the nodes of the next layer to the queue
                if cur.left is not None:
                    q.append(cur.left)
                if cur.right is not None:
                    q.append(cur.right)
            # increment the depth here
            depth += 1
        return depth

func minDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    q := []*TreeNode{root}
    // the root itself is one layer, initialize depth to 1
    depth := 1

    for len(q) > 0 {
        sz := len(q)
        // traverse the nodes of the current layer
        for i := 0; i < sz; i++ {
            cur := q[0]
            q = q[1:]
            // check if we have reached a leaf node
            if cur.Left == nil && cur.Right == nil {
                return depth
            }
            // add the nodes of the next layer to the queue
            if cur.Left != nil {
                q = append(q, cur.Left)
            }
            if cur.Right != nil {
                q = append(q, cur.Right)
            }
        }
        // increment the depth here
        depth++
    }
    return depth
}

var minDepth = function(root) {
    if (root === null) return 0;
    let q = [root];
    // the root itself is one layer, initialize depth to 1
    let depth = 1;

    while (q.length > 0) {
        let sz = q.length;
        // traverse the nodes of the current layer
        for (let i = 0; i < sz; i++) {
            let cur = q.shift();
            // check if we have reached a leaf node
            if (cur.left === null && cur.right === null)
                return depth;
            // add the nodes of the next layer to the queue
            if (cur.left !== null)
                q.push(cur.left);
            if (cur.right !== null)
                q.push(cur.right);
        }
        // increment the depth here
        depth++;
    }
    return depth;
};

When it reaches the second level, it encounters the first leaf node. This leaf node is the one closest to the root, so the algorithm ends at this point.

By clicking on let result =, you can observe the color of the nodes on the binary tree, and clearly see that the BFS algorithm finds the minimum depth without traversing the entire tree.

In summary, you should understand why the BFS algorithm is often used to find the shortest path:

Due to BFS's level-by-level traversal logic, the first time it encounters the target node, the path taken is the shortest. The algorithm may not need to traverse all nodes before it can terminate early.

DFS can also be used to find the shortest path, but it must traverse all nodes to determine the shortest path.

From the perspective of time complexity, both algorithms will traverse all nodes in the worst-case scenario, making their time complexity $O(N)$. However, generally, BFS tends to be more efficient. Therefore, for shortest path problems, BFS is the preferred algorithm.

Why DFS Is Commonly Used to Find All Paths

When dealing with problems that require finding all paths, you'll notice that the Depth-First Search (DFS) algorithm is frequently used, while the Breadth-First Search (BFS) algorithm seems less common.

In theory, both traversal algorithms can be employed. However, the code for finding all paths using BFS tends to be more complex, whereas DFS offers a more straightforward solution.

Consider a binary tree as an example. If you want to use BFS to find all paths (where each path is from the root node to a leaf node), the queue cannot just contain nodes. You would need to adopt a third approach by creating a State class to store the current node and the path leading to it. This is necessary to correctly maintain the path for each node and ultimately compute all paths.

On the other hand, using DFS is simpler. DFS naturally traverses the tree branch by branch from left to right, where each branch represents a path. Thus, DFS is inherently suited for finding all paths.

From the JavaScript code in the visualization panels, it is evident that the BFS algorithm's code is more complex.

In summary, DFS is more commonly used for finding all paths, while BFS is more often utilized for finding the shortest path.