# 二叉树的递归-层序遍历

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.

## Recursive Traversal (DFS)

Framework for traversing binary trees:

```
// 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 short and concise code traverse a binary tree? And in what order does it traverse the tree?

For a recursive traversal function like `traverse`

, you can think of it as a pointer moving through the structure of the binary tree. Below, I've used a visualization to intuitively show you how this function traverses the binary tree.

Open this visualization panel, and the position of the `root`

pointer on the right indicates the current node being accessed, which is the current position of the `traverse`

function. The orange-yellow section shows the stack of the `traverse`

function. You can click the play button in the upper left corner to observe the changes in the position of the `root`

pointer:

The traversal order of the `traverse`

function is to keep moving to the left child node until it encounters a null pointer and cannot move further, then attempt to move one step to the right child node; then keep trying to move to the left child node again, and so on. If both the left and right subtrees are fully traversed, it returns to the parent node above. Actually, you can see from the code that it first recursively calls `root.left`

, and then recursively calls `root.right`

.

**The order of this recursive traversal of nodes is fixed. It is crucial to remember this order; otherwise, you will definitely struggle with the binary tree structure.**

Some readers with a background in data structures might ask: "But Dong, anyone who has taken a data structures course in university has heard of pre-order, in-order, and post-order traversals of binary trees, which produce three different result orders. Why do you say the order of recursive traversal of nodes is fixed here?"

This is a good question. **First of all, the order of recursive traversal, i.e., the order in which the traverse function accesses nodes, is indeed fixed. However, the effect can be different depending on where you write the code in the traverse function.**

For example, when you first enter a node, you don't yet know anything about its child nodes, whereas when you are about to leave a node, you have already traversed all its child nodes. Writing code in these two situations can definitely have different effects.

What you refer to as pre-order, in-order, and post-order traversals are actually just writing code in different positions within the above 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 executes when entering a node; the code at the in-order position executes after traversing the left subtree and before traversing the right subtree; the code at the post-order position executes after traversing both subtrees:

You can open this visualization panel and try the following operations:

Continuously click on the line

`preorderResult.push`

and observe the order in which the`root`

pointer moves on the tree and the elements in`preorderResult`

. This is the pre-order traversal sequence.Reset the visualization panel, continuously click on the line

`inorderResult.push`

, and observe the`root`

pointer's movement and the elements in`inorderResult`

. This is the in-order traversal sequence.Reset the visualization panel, continuously click on the line

`postorderResult.push`

, and observe the`root`

pointer's movement and the elements in`postorderResult`

. This is the post-order traversal sequence.

Understanding the pre-order, in-order, and post-order positions in a binary tree is very important. I will explore the differences and connections between these traversal methods, and how to apply them to backtracking and dynamic programming algorithms in Binary Tree Algorithm Ideas (Overview) and related exercises, so I won't go into depth here.

**Some readers might ask, why does this traverse function first recursively traverse root.left and then root.right? Can it be reversed?**

Of course, it can be reversed. However, the terms pre-order, in-order, and post-order generally assume left-first traversal. This is a conventional habit. If you insist on traversing right first and then left, your understanding of pre-order, in-order, and post-order traversal will differ from the general consensus, which might increase communication costs. Therefore, unless there is a specific need, it is recommended to follow the left-first convention.

In-order Traversal of BST is Ordered

It is important to emphasize that the in-order traversal result of a Binary Search Tree (BST) is ordered. This is a key property of BSTs.

You can observe this by clicking on the line `res.push(root.val);`

in the visualization panel to see the order in which nodes are accessed during in-order traversal:

In the subsequent BST Exercise Collection, some problems will utilize this property.

## Level Order Traversal (BFS)

The above recursive traversal relies on the function stack to recursively traverse the binary tree. If you consider the recursive function `traverse`

as a pointer, then the order in which this pointer moves through the binary tree roughly starts from the far left and goes column by column to the far right.

You can use the visualization panel and click on the line of code `if (root == null)`

to see the order in which the `root`

variable moves through the tree. This will give you a clear view of the order in which the `traverse`

function visits the nodes:

Level order traversal of a binary tree, as the name suggests, means traversing the tree level by level. This traversal method requires the use of a queue, and depending on different needs, there are mainly three different ways to write it. Below are the examples one by one.

### Method One

This is the simplest method, 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);
}
}
}
```

You can open this visualization panel and click on the line of code `console.log(cur.val);`

. You will see that level-order traversal visits the binary tree nodes layer by layer, from left to right:

Pros and Cons of This Approach

The biggest advantage of this approach is its simplicity. You just take the front element out of the queue and then add its left and right children to the queue, that's it.

However, the downside of this approach is that it cannot tell which level the current node is on. Knowing the level of nodes is a common requirement, for example, when you need to collect nodes of each level or calculate the minimum depth of a binary tree.

So, although this approach is simple, it is not used very often. The following method is more commonly used.

### Method Two

With a slight modification to the above solution, we get 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++;
}
};
```

注

Pay attention to the inner for loop in the code:

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

The variable `i`

keeps track of the current position of the node `cur`

in the current level. In most algorithm problems, you won't need this variable, so you can use the following approach instead:

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

This is a matter of personal preference.

**However, make sure to save the queue length sz before starting the loop**, because the length of the queue changes during the loop, and you can't use

`q.size()`

directly as the loop condition.You can open this visualization panel and click on the `console.log`

line of code. You will see that the binary tree nodes are still traversed level by level from left to right, but this time it also prints the level of each node:

This approach can record the level of each node, solving 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? It's to lay the groundwork for more advanced content later.

Right now, we're just discussing level-order traversal of a binary tree. However, level-order traversal of a binary tree can extend to level-order traversal of an N-ary tree, BFS traversal of a graph, and the classic BFS brute-force algorithm framework. So, we need to expand a bit here.

**Recapping Method Two, every time we traverse down one level, we add 1 to depth. You can think of it as each 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 to that node. All nodes in the same level have the same path weight sum**.

Now, if the path weight sum of each branch can be any value, and you need 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 this case, the path weight sums of nodes in the same level may not be the same. Using Method Two, which maintains only a `depth`

variable, won't meet the requirement.

Method Three solves this problem by adding a `State`

class to Method One, allowing each node to maintain its own path weight sum. Here is the code:

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

You can open this visual panel and click on the line of code with `console.log`

. This will allow you to see the tree nodes being traversed layer by layer from left to right, along with the level of each node:

**With this approach, each node has its own depth variable, which is the most flexible and can meet all BFS algorithm needs**. However, defining an additional

`State`

class can be cumbersome, so it's usually sufficient to use the second approach unless necessary.You'll soon learn that scenarios with weighted edges belong to graph algorithms and will be used in the upcoming BFS Algorithm Exercises and Dijkstra's Algorithm.

## Other Traversal Methods?

There are only the two traversal methods mentioned above for binary trees. There may be different ways to write them, but fundamentally, they cannot deviate from these two 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, just manually maintaining a stack to simulate the recursive calls.

Similarly, you might see code that recursively traverses a binary tree layer by layer. But this is essentially level order traversal, just presenting the for loop in the level order traversal code in a recursive format.

In summary, don't be confused by appearances. The traversal methods for binary trees are just these two. Once you master these two methods with the following tutorials and exercises, all brute-force algorithms will be a piece of cake.