PK

PKBytes

Explore tracks
Chapter 24: Tree Fundamentals and Traversal
24.08Intermediate / Advanced5 topics14 min5 interactive animations

General trees

Trees with any number of children: n-ary traversals, parent arrays, the first-child / next-sibling encoding, folder hierarchies and forests.

Learning goals

  • Traverse a tree whose nodes hold lists of children
  • Build a tree from a parent array
  • Convert a general tree into a binary tree and back
  • Print a hierarchy as an indented listing, and handle a forest

Prerequisites

Traversal methodsTree anatomy

Folders, organisation charts and the DOM have nodes with many children. The ideas from binary trees carry over; only the loop over children replaces left and right.

24.08.1

N-ary tree traversal

In an **n-ary tree** a node keeps a list of children. The traversals are the binary ones with a loop in place of the two calls: **preorder** visits the node and then each child in turn, **postorder** visits the children and then the node, and **level order** uses a queue and adds all the children. Inorder is not defined for general trees, since there is no 'between'.

On the parent array “-1 0 0 1 1 2 2 3” (node 0 is the root with children 1 and 2; 1 has children 3 and 4; 2 has 5 and 6; 3 has 7) preorder is [0, 1, 3, 7, 4, 2, 5, 6], postorder is [7, 3, 4, 1, 5, 6, 2, 0] and level order is [0, 1, 2, 3, 4, 5, 6, 7].

Java
1static class Node {
2    int val;
3    List<Node> children = new ArrayList<>();
4    Node(int v) { val = v; }
5}
6static void preorder(Node n, List<Integer> out) {
7    out.add(n.val);
8    for (Node c : n.children) preorder(c, out);
9}
10static void postorder(Node n, List<Integer> out) {
11    for (Node c : n.children) postorder(c, out);
12    out.add(n.val);
13}
14static List<Integer> levelOrder(Node root) {
15    List<Integer> out = new ArrayList<>();
16    Deque<Node> queue = new ArrayDeque<>(List.of(root));
17    while (!queue.isEmpty()) {
18        Node n = queue.poll();
19        out.add(n.val);
20        queue.addAll(n.children);
21    }
22    return out;
23}

Best

O(n)

Average

O(n)

Worst

O(n)

Space

O(h)

General trees from a parent array: traversals and first-child / next-sibling

Interactive · edit the input

Your input

Try

general tree · 8 nodes

0
1
2
3
4
5
6
7
Current nodeOn the call stackVisitedWaiting in the queueLinked
Setup

A general tree node has any number of children, kept in a list, so the traversals loop over the children instead of calling left and right.

Step 1 / 10
Java
1static class Node { int val; List<Node> children = new ArrayList<>(); Node(int v) { val = v; } }
2static Node[] fromParents(int[] parent) {        // parent[i] = index of i's parent, -1 for a root
3    Node[] nodes = new Node[parent.length];
4    for (int i = 0; i < nodes.length; i++) nodes[i] = new Node(i);
5    for (int i = 0; i < nodes.length; i++) if (parent[i] >= 0) nodes[parent[i]].children.add(nodes[i]);
6    return nodes;
7}
8static void preorder(Node n, List<Integer> out) {
9    out.add(n.val);
10    for (Node c : n.children) preorder(c, out);
11}
12static void postorder(Node n, List<Integer> out) {
13    for (Node c : n.children) postorder(c, out);
14    out.add(n.val);
15}
16static List<Integer> levelOrder(Node root) {
17    List<Integer> out = new ArrayList<>();
18    Deque<Node> queue = new ArrayDeque<>(List.of(root));
19    while (!queue.isEmpty()) {
20        Node n = queue.poll();
21        out.add(n.val);
22        queue.addAll(n.children);
23    }
24    return out;
25}
26static void printTree(Node n, int depth, StringBuilder sb) {    // indented listing, like a folder tree
27    sb.append("  ".repeat(depth)).append(n.val).append('\n');
28    for (Node c : n.children) printTree(c, depth + 1, sb);
29}
30static class BNode { int val; BNode firstChild, nextSibling; BNode(int v) { val = v; } }
31static BNode toBinary(Node n) {                  // first child on the left, next sibling on the right
32    BNode b = new BNode(n.val);
33    BNode last = null;
34    for (Node c : n.children) {
35        BNode child = toBinary(c);
36        if (last == null) b.firstChild = child; else last.nextSibling = child;
37        last = child;
38    }
39    return b;
40}

Live state

0 visited

nodes

8

roots

1

No condition evaluated on this step
Execution trace (dry run table)Show 10 steps
StepLineStateWhat happens
1L8nodes=8 roots=1A general tree node has any number of children, kept in a list, so the traversals loop over the children instead of calling left and right.
2L9visited=1Visit 0 before its children.
3L9visited=2Visit 1 before its children.
4L9visited=3Visit 3 before its children.
5L9visited=4Visit 7 before its children.
6L9visited=5Visit 4 before its children.
7L9visited=6Visit 2 before its children.
8L9visited=7Visit 5 before its children.
9L9visited=8Visit 6 before its children.
10L8visited=8Preorder: [0, 1, 3, 7, 4, 2, 5, 6].
24.08.2

Parent array

A tree with n numbered nodes can be stored in an int array where parent[i] is the parent of node i and -1 marks a root. It is the most compact representation: n integers, no objects, and it is the form in which many problems arrive. Going **up** is a single array lookup; going down needs a first pass that builds the children lists.

The array also encodes forests: several -1 entries mean several roots. Validation is worth doing: every value must be -1 or a valid index, and following parents from any node must reach a root and not loop.

Java
1static Node[] fromParents(int[] parent) {            // parent[i] = index of i's parent, -1 for a root
2    Node[] nodes = new Node[parent.length];
3    for (int i = 0; i < nodes.length; i++) nodes[i] = new Node(i);
4    for (int i = 0; i < nodes.length; i++) if (parent[i] >= 0) nodes[parent[i]].children.add(nodes[i]);
5    return nodes;
6}
7static int depthOf(int[] parent, int i) {
8    int d = 0;
9    while (parent[i] != -1) { i = parent[i]; d++; }  // walk up to the root
10    return d;
11}

General trees from a parent array: traversals and first-child / next-sibling

Interactive · edit the input

Your input

Try

general tree · 8 nodes

0
1
2
3
4
5
6
7
Current nodeOn the call stackVisitedWaiting in the queueLinked
Setup

A general tree node has any number of children, kept in a list, so the traversals loop over the children instead of calling left and right.

Step 1 / 10
Java
1static class Node { int val; List<Node> children = new ArrayList<>(); Node(int v) { val = v; } }
2static Node[] fromParents(int[] parent) {        // parent[i] = index of i's parent, -1 for a root
3    Node[] nodes = new Node[parent.length];
4    for (int i = 0; i < nodes.length; i++) nodes[i] = new Node(i);
5    for (int i = 0; i < nodes.length; i++) if (parent[i] >= 0) nodes[parent[i]].children.add(nodes[i]);
6    return nodes;
7}
8static void preorder(Node n, List<Integer> out) {
9    out.add(n.val);
10    for (Node c : n.children) preorder(c, out);
11}
12static void postorder(Node n, List<Integer> out) {
13    for (Node c : n.children) postorder(c, out);
14    out.add(n.val);
15}
16static List<Integer> levelOrder(Node root) {
17    List<Integer> out = new ArrayList<>();
18    Deque<Node> queue = new ArrayDeque<>(List.of(root));
19    while (!queue.isEmpty()) {
20        Node n = queue.poll();
21        out.add(n.val);
22        queue.addAll(n.children);
23    }
24    return out;
25}
26static void printTree(Node n, int depth, StringBuilder sb) {    // indented listing, like a folder tree
27    sb.append("  ".repeat(depth)).append(n.val).append('\n');
28    for (Node c : n.children) printTree(c, depth + 1, sb);
29}
30static class BNode { int val; BNode firstChild, nextSibling; BNode(int v) { val = v; } }
31static BNode toBinary(Node n) {                  // first child on the left, next sibling on the right
32    BNode b = new BNode(n.val);
33    BNode last = null;
34    for (Node c : n.children) {
35        BNode child = toBinary(c);
36        if (last == null) b.firstChild = child; else last.nextSibling = child;
37        last = child;
38    }
39    return b;
40}

Live state

0 visited

nodes

8

roots

1

No condition evaluated on this step
Execution trace (dry run table)Show 10 steps
StepLineStateWhat happens
1L8nodes=8 roots=1A general tree node has any number of children, kept in a list, so the traversals loop over the children instead of calling left and right.
2L9visited=1Visit 0 before its children.
3L9visited=2Visit 1 before its children.
4L9visited=3Visit 3 before its children.
5L9visited=4Visit 7 before its children.
6L9visited=5Visit 4 before its children.
7L9visited=6Visit 2 before its children.
8L9visited=7Visit 5 before its children.
9L9visited=8Visit 6 before its children.
10L8visited=8Preorder: [0, 1, 3, 7, 4, 2, 5, 6].
24.08.3

First-child/next-sibling

Every general tree can be stored as a **binary tree** with the **first-child / next-sibling** encoding: the left link of a node points to its first child, and the right link points to its next sibling. A node's children are then the left child followed by the chain of right links. The result has the same n nodes and no new ones, so general-tree problems can reuse binary-tree code.

The “First-child / next-sibling” preset converts “-1 0 0 0 1 1” (node 0 has children 1, 2 and 3; node 1 has children 4 and 5): node 1 is the left child of 0, node 2 the right child of 1, node 3 the right child of 2, node 4 the left child of 1, and node 5 the right child of 4. The binary tree's height is not the general tree's height: wide trees become tall.

Java
1static class BNode {
2    int val;
3    BNode firstChild, nextSibling;
4    BNode(int v) { val = v; }
5}
6static BNode toBinary(Node n) {                      // first child on the left, next sibling on the right
7    BNode b = new BNode(n.val);
8    BNode last = null;
9    for (Node c : n.children) {
10        BNode child = toBinary(c);
11        if (last == null) b.firstChild = child; else last.nextSibling = child;
12        last = child;
13    }
14    return b;
15}

General trees from a parent array: traversals and first-child / next-sibling

Interactive · edit the input

Your input

Try

general tree · 8 nodes

0
1
2
3
4
5
6
7
Current nodeOn the call stackVisitedWaiting in the queueLinked
Setup

A general tree node has any number of children, kept in a list, so the traversals loop over the children instead of calling left and right.

Step 1 / 10
Java
1static class Node { int val; List<Node> children = new ArrayList<>(); Node(int v) { val = v; } }
2static Node[] fromParents(int[] parent) {        // parent[i] = index of i's parent, -1 for a root
3    Node[] nodes = new Node[parent.length];
4    for (int i = 0; i < nodes.length; i++) nodes[i] = new Node(i);
5    for (int i = 0; i < nodes.length; i++) if (parent[i] >= 0) nodes[parent[i]].children.add(nodes[i]);
6    return nodes;
7}
8static void preorder(Node n, List<Integer> out) {
9    out.add(n.val);
10    for (Node c : n.children) preorder(c, out);
11}
12static void postorder(Node n, List<Integer> out) {
13    for (Node c : n.children) postorder(c, out);
14    out.add(n.val);
15}
16static List<Integer> levelOrder(Node root) {
17    List<Integer> out = new ArrayList<>();
18    Deque<Node> queue = new ArrayDeque<>(List.of(root));
19    while (!queue.isEmpty()) {
20        Node n = queue.poll();
21        out.add(n.val);
22        queue.addAll(n.children);
23    }
24    return out;
25}
26static void printTree(Node n, int depth, StringBuilder sb) {    // indented listing, like a folder tree
27    sb.append("  ".repeat(depth)).append(n.val).append('\n');
28    for (Node c : n.children) printTree(c, depth + 1, sb);
29}
30static class BNode { int val; BNode firstChild, nextSibling; BNode(int v) { val = v; } }
31static BNode toBinary(Node n) {                  // first child on the left, next sibling on the right
32    BNode b = new BNode(n.val);
33    BNode last = null;
34    for (Node c : n.children) {
35        BNode child = toBinary(c);
36        if (last == null) b.firstChild = child; else last.nextSibling = child;
37        last = child;
38    }
39    return b;
40}

Live state

0 visited

nodes

8

roots

1

No condition evaluated on this step
Execution trace (dry run table)Show 10 steps
StepLineStateWhat happens
1L8nodes=8 roots=1A general tree node has any number of children, kept in a list, so the traversals loop over the children instead of calling left and right.
2L9visited=1Visit 0 before its children.
3L9visited=2Visit 1 before its children.
4L9visited=3Visit 3 before its children.
5L9visited=4Visit 7 before its children.
6L9visited=5Visit 4 before its children.
7L9visited=6Visit 2 before its children.
8L9visited=7Visit 5 before its children.
9L9visited=8Visit 6 before its children.
10L8visited=8Preorder: [0, 1, 3, 7, 4, 2, 5, 6].
24.08.4

Folder hierarchy

A file system is a tree: folders are internal nodes and files are leaves. An **indented listing**, like the output of the tree command, is a preorder traversal that passes the depth down and indents each line by it. Sizes work as postorder: a folder's size is its own plus the sizes of its children, computed after the children return.

The “Folder listing” preset prints the parent array “-1 0 0 1 1 2 4” with each dot marking one level of nesting. The same two traversals answer most folder questions: listing and totalling.

Java
1static void printTree(Node n, int depth, StringBuilder sb) {     // preorder with the depth passed down
2    sb.append("  ".repeat(depth)).append(n.val).append('\n');
3    for (Node c : n.children) printTree(c, depth + 1, sb);
4}
5static int totalSize(Node n, int[] size) {                       // postorder: children first
6    int total = size[n.val];
7    for (Node c : n.children) total += totalSize(c, size);
8    return total;
9}

General trees from a parent array: traversals and first-child / next-sibling

Interactive · edit the input

Your input

Try

general tree · 8 nodes

0
1
2
3
4
5
6
7
Current nodeOn the call stackVisitedWaiting in the queueLinked
Setup

A general tree node has any number of children, kept in a list, so the traversals loop over the children instead of calling left and right.

Step 1 / 10
Java
1static class Node { int val; List<Node> children = new ArrayList<>(); Node(int v) { val = v; } }
2static Node[] fromParents(int[] parent) {        // parent[i] = index of i's parent, -1 for a root
3    Node[] nodes = new Node[parent.length];
4    for (int i = 0; i < nodes.length; i++) nodes[i] = new Node(i);
5    for (int i = 0; i < nodes.length; i++) if (parent[i] >= 0) nodes[parent[i]].children.add(nodes[i]);
6    return nodes;
7}
8static void preorder(Node n, List<Integer> out) {
9    out.add(n.val);
10    for (Node c : n.children) preorder(c, out);
11}
12static void postorder(Node n, List<Integer> out) {
13    for (Node c : n.children) postorder(c, out);
14    out.add(n.val);
15}
16static List<Integer> levelOrder(Node root) {
17    List<Integer> out = new ArrayList<>();
18    Deque<Node> queue = new ArrayDeque<>(List.of(root));
19    while (!queue.isEmpty()) {
20        Node n = queue.poll();
21        out.add(n.val);
22        queue.addAll(n.children);
23    }
24    return out;
25}
26static void printTree(Node n, int depth, StringBuilder sb) {    // indented listing, like a folder tree
27    sb.append("  ".repeat(depth)).append(n.val).append('\n');
28    for (Node c : n.children) printTree(c, depth + 1, sb);
29}
30static class BNode { int val; BNode firstChild, nextSibling; BNode(int v) { val = v; } }
31static BNode toBinary(Node n) {                  // first child on the left, next sibling on the right
32    BNode b = new BNode(n.val);
33    BNode last = null;
34    for (Node c : n.children) {
35        BNode child = toBinary(c);
36        if (last == null) b.firstChild = child; else last.nextSibling = child;
37        last = child;
38    }
39    return b;
40}

Live state

0 visited

nodes

8

roots

1

No condition evaluated on this step
Execution trace (dry run table)Show 10 steps
StepLineStateWhat happens
1L8nodes=8 roots=1A general tree node has any number of children, kept in a list, so the traversals loop over the children instead of calling left and right.
2L9visited=1Visit 0 before its children.
3L9visited=2Visit 1 before its children.
4L9visited=3Visit 3 before its children.
5L9visited=4Visit 7 before its children.
6L9visited=5Visit 4 before its children.
7L9visited=6Visit 2 before its children.
8L9visited=7Visit 5 before its children.
9L9visited=8Visit 6 before its children.
10L8visited=8Preorder: [0, 1, 3, 7, 4, 2, 5, 6].
24.08.5

Forest traversal

A forest is traversed by traversing each of its trees in turn: loop over the roots and call the tree traversal on each, or add a virtual root whose children are the real roots, so one call handles everything. Level order starts with all roots in the queue.

The “A forest (two roots)” preset has the parent array “-1 0 -1 2 2 0”: root 0 (with children 1 and 5) and root 2 (with children 3 and 4). Preorder gives [0, 1, 5, 2, 3, 4]: the first tree fully, then the second.

Java
1static List<Integer> forestPreorder(int[] parent) {
2    Node[] nodes = fromParents(parent);
3    List<Integer> out = new ArrayList<>();
4    for (int i = 0; i < parent.length; i++) {
5        if (parent[i] == -1) preorder(nodes[i], out);        // one traversal per root
6    }
7    return out;
8}
9static Node[] fromParents(int[] parent) {
10    Node[] nodes = new Node[parent.length];
11    for (int i = 0; i < nodes.length; i++) nodes[i] = new Node(i);
12    for (int i = 0; i < nodes.length; i++) if (parent[i] >= 0) nodes[parent[i]].children.add(nodes[i]);
13    return nodes;
14}
15static void preorder(Node n, List<Integer> out) {
16    out.add(n.val);
17    for (Node c : n.children) preorder(c, out);
18}

General trees from a parent array: traversals and first-child / next-sibling

Interactive · edit the input

Your input

Try

general tree · 8 nodes

0
1
2
3
4
5
6
7
Current nodeOn the call stackVisitedWaiting in the queueLinked
Setup

A general tree node has any number of children, kept in a list, so the traversals loop over the children instead of calling left and right.

Step 1 / 10
Java
1static class Node { int val; List<Node> children = new ArrayList<>(); Node(int v) { val = v; } }
2static Node[] fromParents(int[] parent) {        // parent[i] = index of i's parent, -1 for a root
3    Node[] nodes = new Node[parent.length];
4    for (int i = 0; i < nodes.length; i++) nodes[i] = new Node(i);
5    for (int i = 0; i < nodes.length; i++) if (parent[i] >= 0) nodes[parent[i]].children.add(nodes[i]);
6    return nodes;
7}
8static void preorder(Node n, List<Integer> out) {
9    out.add(n.val);
10    for (Node c : n.children) preorder(c, out);
11}
12static void postorder(Node n, List<Integer> out) {
13    for (Node c : n.children) postorder(c, out);
14    out.add(n.val);
15}
16static List<Integer> levelOrder(Node root) {
17    List<Integer> out = new ArrayList<>();
18    Deque<Node> queue = new ArrayDeque<>(List.of(root));
19    while (!queue.isEmpty()) {
20        Node n = queue.poll();
21        out.add(n.val);
22        queue.addAll(n.children);
23    }
24    return out;
25}
26static void printTree(Node n, int depth, StringBuilder sb) {    // indented listing, like a folder tree
27    sb.append("  ".repeat(depth)).append(n.val).append('\n');
28    for (Node c : n.children) printTree(c, depth + 1, sb);
29}
30static class BNode { int val; BNode firstChild, nextSibling; BNode(int v) { val = v; } }
31static BNode toBinary(Node n) {                  // first child on the left, next sibling on the right
32    BNode b = new BNode(n.val);
33    BNode last = null;
34    for (Node c : n.children) {
35        BNode child = toBinary(c);
36        if (last == null) b.firstChild = child; else last.nextSibling = child;
37        last = child;
38    }
39    return b;
40}

Live state

0 visited

nodes

8

roots

1

No condition evaluated on this step
Execution trace (dry run table)Show 10 steps
StepLineStateWhat happens
1L8nodes=8 roots=1A general tree node has any number of children, kept in a list, so the traversals loop over the children instead of calling left and right.
2L9visited=1Visit 0 before its children.
3L9visited=2Visit 1 before its children.
4L9visited=3Visit 3 before its children.
5L9visited=4Visit 7 before its children.
6L9visited=5Visit 4 before its children.
7L9visited=6Visit 2 before its children.
8L9visited=7Visit 5 before its children.
9L9visited=8Visit 6 before its children.
10L8visited=8Preorder: [0, 1, 3, 7, 4, 2, 5, 6].

Practice ladder

Now try it yourself

Easy

  • N-ary Tree Preorder Traversal
  • N-ary Tree Postorder Traversal
  • Maximum Depth of N-ary Tree

Medium

  • N-ary Tree Level Order Traversal
  • Serialize and Deserialize N-ary Tree
  • Time Needed to Inform All Employees

Advanced

  • Encode N-ary Tree to Binary Tree
  • Delete Nodes And Return Forest

Key takeaways

  • General-tree traversals replace the left and right calls with a loop over the children list.
  • A parent array stores a tree or forest in n integers: -1 marks a root, and going up is one lookup.
  • First-child / next-sibling turns any tree into a binary tree with the same nodes.
  • A folder listing is preorder with the depth passed down; sizes are a postorder sum.
  • Traverse a forest by looping over its roots.