N-ary Tree Recursive/Level Traversal

labuladongOriginalAbout 2005 words

Prerequisite Knowledge

Before reading this article, you should first learn:

Recursive/Level-order Traversal of Binary Trees

Summary in One Sentence

A multi-way tree structure is an extension of the binary tree structure, where a binary tree is a special case of a multi-way tree. A forest refers to a collection of multiple multi-way trees.

Traversing a multi-way tree is an extension of binary tree traversal.

The nodes of a binary tree look like this, with each node having two child nodes:

java 🟢

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

cpp 🤖

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

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

python 🤖

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

go 🤖

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

javascript 🤖

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

A node in an n-ary tree looks like this, where each node has an arbitrary number of child nodes:

java 🟢

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

cpp 🤖

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

python 🤖

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

go 🤖

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

javascript 🤖

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

That's the only difference, nothing else.

Forest

Here, let's introduce the term "forest," which will be used later when discussing the Union-Find algorithm.

Simply put, a forest is a collection of multiple multi-way trees. A single multi-way tree is actually a special kind of forest.

In the Union-Find algorithm, we often manage root nodes of several multi-way trees simultaneously, and the collection of these root nodes is called a forest.

Next, let's talk about traversing multi-way trees, which, like binary trees, can be done using two methods: recursive traversal (DFS) and level-order traversal (BFS).

Recursive Traversal (DFS)

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

java 🟢

// traversal framework for binary tree
void traverse(TreeNode root) {
    if (root == null) {
        return;
    }
    // pre-order position
    traverse(root.left);
    // in-order position
    traverse(root.right);
    // post-order position
}

// traversal framework for N-ary tree
void traverse(Node root) {
    if (root == null) {
        return;
    }
    // pre-order position
    for (Node child : root.children) {
        traverse(child);
    }
    // post-order position
}

cpp 🤖

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

// N-ary tree traversal framework
void traverse(Node* root) {
    if (root == nullptr) {
        return;
    }
    // pre-order position
    for (Node* child : root->children) {
        traverse(child);
    }
    // post-order position
}

python 🤖

# traversal framework for binary trees
def traverse_binary_tree(root):
    if root is None:
        return
    # pre-order position
    traverse_binary_tree(root.left)
    # in-order position
    traverse_binary_tree(root.right)
    # post-order position


# traversal framework for N-ary trees
def traverse_n_ary_tree(root):
    if root is None:
        return
    # pre-order position
    for child in root.children:
        traverse_n_ary_tree(child)
    # post-order position

go 🤖

// Traversal framework for binary tree
func traverse(root *TreeNode) {
    if root == nil {
        return
    }
    // Preorder position
    traverse(root.Left)
    // Inorder position
    traverse(root.Right)
    // Postorder position
}

// Traversal framework for N-ary tree
func traverseNary(root *Node) {
    if root == nil {
        return
    }
    // Preorder position
    for _, child := range root.Children {
        traverseNary(child)
    }
    // Postorder position
}

javascript 🤖

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

// N-ary tree traversal framework
var traverse = function(root) {
    if (root === null) {
        return;
    }
    // pre-order position
    for (var i = 0; i < root.children.length; i++) {
        traverse(root.children[i]);
    }
    // post-order position
};

The only difference is that an n-ary tree does not have an in-order position, because there may be multiple nodes, making the concept of an in-order position meaningless.

Take a look at the visualization panel below. Click on the code parts labeled preorderResult.push or postorderResult.push to observe the execution order of pre-order and post-order traversals. It's actually the same as with binary trees:

Level-order Traversal (BFS)

The level-order traversal of an n-ary tree is the same as level-order traversal of a binary tree; both use a queue. The only difference is that instead of left and right children, you consider all children of the n-ary tree. Therefore, there are three methods for level-order traversal of an n-ary tree. Let's look at them one by one.

Method One

The first method for level-order traversal:

java 🟢

void levelOrderTraverse(Node root) {
    if (root == null) {
        return;
    }
    Queue<Node> q = new LinkedList<>();
    q.offer(root);
    while (!q.isEmpty()) {
        Node cur = q.poll();
        // visit the cur node
        System.out.println(cur.val);

        // add all children of cur to the queue
        for (Node child : cur.children) {
            q.offer(child);
        }
    }
}

cpp 🤖

void levelOrderTraverse(Node* root) {
    if (root == nullptr) {
        return;
    }
    std::queue<Node*> q;
    q.push(root);
    while (!q.empty()) {
        Node* cur = q.front();
        q.pop();
        // visit the cur node
        std::cout << cur->val << std::endl;

        // add all children of cur to the queue
        for (Node* child : cur->children) {
            q.push(child);
        }
    }
}

python 🤖

from collections import deque

def level_order_traverse(root):
    if root is None:
        return
    
    q = deque()
    q.append(root)
    
    while q:
        cur = q.popleft()
        # visit the cur node
        print(cur.val)
        
        # add all child nodes of cur to the queue
        for child in cur.children:
            q.append(child)

go 🤖

func levelOrderTraverse(root *Node) {
	if root == nil {
		return
	}
	q := []*Node{}
	q = append(q, root)
	for len(q) > 0 {
		cur := q[0]
		q = q[1:]
		// visit cur node
		fmt.Println(cur.Val)

		// add all children of cur to the queue
		for _, child := range cur.Children {
			q = append(q, child)
		}
	}
}

javascript 🤖

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 all child nodes of cur to the queue
        for (var child of cur.children) {
            q.push(child);
        }
    }
}

Method Two

The second method for level-order traversal that can record the depth of nodes:

java 🟢

void levelOrderTraverse(Node root) {
    if (root == null) {
        return;
    }
    Queue<Node> q = new LinkedList<>();
    q.offer(root);
    // Record the current depth being traversed (root node is considered level 1)
    int depth = 1;

    while (!q.isEmpty()) {
        int sz = q.size();
        for (int i = 0; i < sz; i++) {
            Node cur = q.poll();
            // Visit the cur node and know its level
            System.out.println("depth = " + depth + ", val = " + cur.val);

            for (Node child : cur.children) {
                q.offer(child);
            }
        }
        depth++;
    }
}

cpp 🤖

#include <iostream>
#include <queue>
#include <vector>

void levelOrderTraverse(Node* root) {
    if (root == nullptr) {
        return;
    }
    std::queue<Node*> q;
    q.push(root);
    // record the current level being traversed (root node is considered level 1)
    int depth = 1;

    while (!q.empty()) {
        int sz = q.size();
        for (int i = 0; i < sz; i++) {
            Node* cur = q.front();
            q.pop();
            // visit the cur node and know its level
            std::cout << "depth = " << depth << ", val = " << cur->val << std::endl;

            for (Node* child : cur->children) {
                q.push(child);
            }
        }
        depth++;
    }
}

python 🤖

from collections import deque

def levelOrderTraverse(root):
    if root is None:
        return
    q = deque()
    q.append(root)
    # record the current level being traversed (root node is considered level 1)
    depth = 1

    while q:
        sz = len(q)
        for i in range(sz):
            cur = q.popleft()
            # visit the cur node and know the level it is on
            print(f"depth = {depth}, val = {cur.val}")

            for child in cur.children:
                q.append(child)
        depth += 1

go 🤖

func levelOrderTraverse(root *Node) {
    if root == nil {
        return
    }
    q := []*Node{root}
    // record the current depth being traversed (root node is considered as level 1)
    depth := 1

    for len(q) > 0 {
        sz := len(q)
        for i := 0; i < sz; i++ {
            cur := q[0]
            q = q[1:]
            // visit the cur node and know its depth
            fmt.Printf("depth = %d, val = %d\n", depth, cur.val)

            for _, child := range cur.children {
                q = append(q, child)
            }
        }
        depth++
    }
}

javascript 🤖

var levelOrderTraverse = function(root) {
    if (root === null) {
        return;
    }
    var q = [];
    q.push(root);
    // record the current depth being traversed (root node is considered 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 level
            console.log("depth = " + depth + ", val = " + cur.val);

            for (var j = 0; j < cur.children.length; j++) {
                q.push(cur.children[j]);
            }
        }
        depth++;
    }
}

Method Three

The third method that can adapt to edges with different weights:

java 🟢

class State {
    Node node;
    int depth;

    public State(Node node, int depth) {
        this.node = node;
        this.depth = depth;
    }
}

void levelOrderTraverse(Node root) {
    if (root == null) {
        return;
    }
    Queue<State> q = new LinkedList<>();
    // record the current depth of traversal (root node is considered as level 1)
    q.offer(new State(root, 1));

    while (!q.isEmpty()) {
        State state = q.poll();
        Node cur = state.node;
        int depth = state.depth;
        // visit the cur node while knowing its depth
        System.out.println("depth = " + depth + ", val = " + cur.val);

        for (Node child : cur.children) {
            q.offer(new State(child, depth + 1));
        }
    }
}

cpp 🤖

class State {
public:
    Node* node;
    int depth;

    State(Node* node, int depth) : node(node), depth(depth) {}
};

void levelOrderTraverse(Node* root) {
    if (root == nullptr) {
        return;
    }
    std::queue<State> q;
    // Record the current level being traversed (root node is considered as level 1)
    q.push(State(root, 1));

    while (!q.empty()) {
        State state = q.front();
        q.pop();
        Node* cur = state.node;
        int depth = state.depth;
        // Visit the cur node and know its level
        std::cout << "depth = " << depth << ", val = " << cur->val << std::endl;

        for (Node* child : cur->children) {
            q.push(State(child, depth + 1));
        }
    }
}

python 🤖

class State:
    def __init__(self, node, depth):
        self.node = node
        self.depth = depth

def levelOrderTraverse(root):
    if root is None:
        return
    q = deque()
    # Record the current level being traversed (root node is considered as level 1)
    q.append(State(root, 1))

    while q:
        state = q.popleft()
        cur = state.node
        depth = state.depth
        # Visit the cur node while knowing its level
        print(f"depth = {depth}, val = {cur.val}")

        for child in cur.children:
            q.append(State(child, depth + 1))

go 🤖

type State struct {
    node  *Node
    depth int
}

func levelOrderTraverse(root *Node) {
    if root == nil {
        return
    }
    q := []State{}
    // record the current level being traversed (root node is considered as level 1)
    q = append(q, State{root, 1})

    for len(q) > 0 {
        state := q[0]
        q = q[1:]
        cur := state.node
        depth := state.depth
        // visit the cur node and know its level
        fmt.Printf("depth = %d, val = %d\n", depth, cur.Val)

        for _, child := range cur.Children {
            q = append(q, State{child, depth + 1})
        }
    }
}

javascript 🤖

function State(node, depth) {
    this.node = node;
    this.depth = depth;
}

var levelOrderTraverse = function(root) {
    if (root === null) {
        return;
    }
    var q = [];
    // record the current level being traversed (consider the root node as level 1)
    q.push(new State(root, 1));

    while (q.length !== 0) {
        var state = q.shift();
        var cur = state.node;
        var depth = state.depth;
        // visit the cur node and know its level
        console.log("depth = " + depth + ", val = " + cur.val);

        for (var i = 0; i < cur.children.length; i++) {
            q.push(new State(cur.children[i], depth + 1));
        }
    }
}

Nothing much to say. If there's anything unclear, refer to the level-order traversal code and visualization panel in the previous article Binary Tree Traversal.