N-ary Tree Recursive/Level Traversal

A node in a binary tree 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 node in a multi-way tree 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 me explain what "forest" means. Later, when we talk about the Union Find algorithm, this concept will be useful.

As the name suggests, a forest is a collection of multiple multi-way trees (even a single tree is a special kind of forest). In code, it is just a list of the root nodes of several multi-way trees, like this:

List<Node> forest;

You just need to run DFS or BFS on each root node, and you will visit all the nodes in the forest.

In the union-find algorithm, we often keep the root nodes of several multi-way trees. These roots together form a forest.

Now, let's talk about traversal of a multi-way tree. Just like a binary tree, there are only two types: recursive traversal (DFS) and level order traversal (BFS).

Recursive Traversal (DFS)

Let's compare the frameworks for traversing binary trees and multi-way trees:

Level Order Traversal (BFS)

Method One

Method Two

Method Three