N-ary Tree Recursive/Level Traversal

A binary tree node looks like this. Each node has two children:

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-way tree node looks like this. Each node can have any number of children:

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.

Forest

Let’s talk about the term "forest". We will use this concept later when learning about Union Find algorithm.

A forest is a collection of multiple multi-way trees (and a single multi-way tree is also a special forest). In code, it's just a list of root nodes for multi-way trees, like this:

List<TreeNode> forest;

You just need to do DFS or BFS traversal starting from each root node to traverse all nodes in the forest.

In the union-find algorithm, we may have multiple root nodes at the same time. The set of these roots forms a forest.

Now let's talk about traversing a multi-way tree. Like binary trees, there are only two main ways: recursive traversal (DFS) and level order traversal (BFS).

Recursive Traversal (DFS)

Let’s compare the traversal of multi-way trees with the binary tree traversal framework:

Level Order Traversal (BFS)

Method One

Method Two

Method Three