N-ary Tree Recursive/Level Traversal

A binary tree node looks like this, with each node having two child nodes:

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
}

class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;

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

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

var TreeNode = function(val) {
    this.val = val;
    this.left = null;
    this.right = null;
};

A multi-tree node looks like this, with each node having any number of child nodes:

class Node {
    int val;
    List<Node> children;
}

class Node {
public:
    int val;
    vector<Node*> children;
};

class Node:
    def __init__(self, val: int):
        self.val = val
        self.children = []

type Node struct {
    val      int
    children []*Node
}

var Node = function(val) {
    this.val = val;
    this.children = [];
}

That's the only difference, nothing else.

Forest

Here we introduce the term "forest," which will be used later in the Union Find Disjoint Set Algorithm.

Simply put, a forest is a collection of multiple multi-trees. A single multi-tree is essentially a special type of forest.

In the disjoint set algorithm, we simultaneously hold the root nodes of multiple multi-trees, and these root nodes collectively form a forest.

Next, let's talk about multi-tree traversal, which, like binary trees, includes recursive traversal (DFS) and level order traversal (BFS).

Recursive Traversal (DFS)

Let's compare the traversal framework of binary trees with that of multi-trees: