Skip to content
Tutorials Center
My learning

Topics

Lesson 92 of 225 ยท Trees

N-ary Trees: Depth, Diameter, Mirror, Serialize

Work with trees where a node has any number of children: height, diameter, mirror, serialization, and the first-child/next-sibling trick that turns them binary.

Binary trees give every node at most two children, which is neat for searching but unnatural for much real data. A folder can hold any number of files, an HTML element any number of child elements, a company any number of direct reports. These shapes are N-ary trees (also called general trees or rooted trees): each node holds a value and a list of children.

Everything you know about binary trees still applies; only the "left and right" recursion becomes a loop over the children. This lesson builds the node class, solves the classic measurements (size, depth, diameter), mirrors and serializes a tree, and ends with the first-child / next-sibling trick that stores any N-ary tree using binary nodes.

The node and a sample tree

Python
class Node:
    def __init__(self, val, children=None):
        self.val = val
        self.children = children or []

We will reuse this tree, written so that the shape is visible in the code:

TEXT
        1
      / | \
     2  3  4
    /|     |
   5 6     7
           |
           8

Size, depth and height

For a node, the height is the length of the longest path down to a leaf (a leaf has height 0 here), and its depth is the distance from the root. Both are one-line recursions.

  • size(node) = 1 + sum(size(c) for c in children)
  • height(node) = 0 if no children, else 1 + max(height(c))

For very deep trees, Python's recursion limit (about 1000 frames) can be a problem; the second TryIt below shows an iterative version that uses a queue, the same pattern as tree BFS.

Python Size, height and level order

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Diameter

The diameter is the number of edges on the longest path between any two nodes. As with binary trees, the longest path has a highest node, and through that node the best path joins its two tallest child branches. So at each node compute the height of every child, keep the two largest, and the candidate is top1 + top2 + 2 (edges counted, since each branch adds one edge to reach the node). Take the maximum over all nodes.

Doing that in one pass returns the height up and updates the best diameter on the side.

Python Diameter in one traversal

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The longest path in the sample is 8 - 7 - 4 - 1 - 2 - 5 (or ending at 6): 5 edges, 6 nodes.

Mirror

Mirroring an N-ary tree reverses the order of the children at every level. Recursion: mirror every child first, then reverse the list. It runs in O(n) and can be done in place.

Serialize and deserialize

To store a tree in a flat list or string you need to recover the shape later. For a binary tree, null markers do the job. For an N-ary tree, two compact formats are common:

  • Preorder with child counts: write each value followed by how many children it has. Reading is a single recursive pass: read a value and a count, then read that many subtrees.
  • Preorder with an end marker: write the value, then the children, then a special ) token that means "no more children here".

Both are O(n), and the child-count version needs no marker characters in the values.

Python Mirror and serialize with child counts

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

First-child / next-sibling

A node with an unknown number of children needs a list. There is a classic trick to avoid that: give every node exactly two links, one to its first child and one to its next sibling (the next child of the same parent). The result is a binary tree that stores exactly the same information. Going down means "first child", going right means "next sibling".

TEXT
N-ary tree            first_child        next_sibling
1: children 2, 3, 4    1 -> 2             (none)
2: children 5, 6       2 -> 5             2 -> 3
3: leaf                (none)             3 -> 4
4: child 7             4 -> 7             (none)
5, 6: leaves           (none)             5 -> 6
7: leaf                (none)             (none)

Why care? Every algorithm for binary trees now applies to any tree, memory is predictable (two pointers per node), and this representation is used in file-system code and some parsers. The cost is that the left-child depth no longer equals the original depth: moving right is a sibling step, which stays at the same level in the original tree.

Python Convert to first-child/next-sibling and back

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Common mistakes

  • Treating an empty children list as None. Keep the list always present, so loops need no special case.
  • Writing max(height(c) for c in node.children) on a leaf: max() of an empty sequence raises an error. Check for leaves first or pass default=-1.
  • Mixing up diameter in nodes and in edges. State which one the problem asks for.
  • Sharing the same list object as the default argument. Use children or [], never children=[].
  • Assuming recursion is always safe: a degenerate tree can be thousands of levels deep.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What data structure does a node in an N-ary tree typically use to reach its children?

    Because the number of children varies, a list of children is the natural choice. A binary tree is the special case with at most two.
  2. 2. In the one-pass diameter algorithm, what is the candidate path length through a node (in edges), given its two tallest child heights h1 and h2, with leaf height 0?

    Each of the two branches contributes its height plus one edge connecting its child to the node, so the path has h1 + 1 + h2 + 1 edges.
  3. 3. How does the 'preorder with child counts' format recover the tree shape?

    The count tells the reader exactly how many subtrees follow the value, so no marker characters are needed.
  4. 4. In the first-child / next-sibling representation, what does the right pointer of a node mean?

    Left means first child and right means next sibling, so moving right stays on the same level of the original tree.

Summary

  • An N-ary tree node keeps a value and a list of children; every binary tree recursion turns into a loop over the children.
  • size and height are one-line recursions; use a queue for very deep trees.
  • The diameter combines the two tallest child branches at each node, found in a single traversal.
  • Mirroring reverses the child list at every node.
  • Serialize with preorder plus child counts (or an end marker) and rebuild with one recursive read.
  • First-child / next-sibling stores any tree with two pointers per node, turning it into a binary tree.

Next: Binary Search Tree Problems