# 6.5 General Trees (Left-Child, Right-Sibling)

> Trees where a node can have any number of children, stored with only two pointers per node using the left-child/right-sibling representation.

Chapter: Trees · ~30 min · medium
URL: https://dsa.fetehadin.com/learn/general-trees

## Mental model

A **folder on your computer** can hold any number of files and sub-folders. A **company** boss can manage 2 people or 20. These are **general trees** (also called n-ary trees): a node can have **any number** of children.

### The storage problem

A binary tree node has exactly two child pointers. For a general tree, how many should we reserve? Ten? Most would be `nullptr` and wasted, and an eleventh child would not fit.

### The fix: left-child, right-sibling

Give each node just **two** pointers:

```cpp
struct GNode {
    char data;
    GNode* firstChild;    // the leftmost child
    GNode* nextSibling;   // the next brother to the right
};
```

Each parent points only to its **first** child. The children of one parent are chained together like a **linked list** through `nextSibling`.

So "A has children B, C, D" becomes: `A.firstChild = B`, `B.nextSibling = C`, `C.nextSibling = D`.

### It's secretly a binary tree

Rename `firstChild` to `left` and `nextSibling` to `right` and you have a binary tree. That is why this is also called the **binary tree representation of a general tree**. Exams often ask you to draw it: children go **down-left**, siblings go **across to the right**.

## C++ code: general-tree.cpp

```cpp
#include <iostream>
#include <string>
using namespace std;

struct GNode {
    char data;
    GNode* firstChild;    // leftmost child
    GNode* nextSibling;   // next brother to the right
};

GNode* make(char c) { return new GNode{c, nullptr, nullptr}; }

void addChild(GNode* parent, GNode* child) {
    if (!parent->firstChild) { parent->firstChild = child; return; }
    GNode* s = parent->firstChild;
    while (s->nextSibling) s = s->nextSibling;
    s->nextSibling = child;
}

void print(GNode* n, int depth) {          // preorder with indentation
    if (n == nullptr) return;
    cout << string(depth * 2, ' ') << n->data << "\n";
    print(n->firstChild, depth + 1);
    print(n->nextSibling, depth);
}

int countChildren(GNode* n) {
    int c = 0;
    for (GNode* k = n->firstChild; k; k = k->nextSibling) c++;
    return c;
}

void destroy(GNode* n) { if (!n) return; destroy(n->firstChild); destroy(n->nextSibling); delete n; }

int main() {
    GNode *A = make('A'), *B = make('B'), *C = make('C'), *D = make('D');
    addChild(A, B); addChild(A, C); addChild(A, D);
    addChild(B, make('E')); addChild(B, make('F'));
    addChild(D, make('G')); addChild(D, make('H')); addChild(D, make('I'));
    print(A, 0);
    cout << "children of A: " << countChildren(A) << ", of D: " << countChildren(D) << "\n";
    destroy(A);
}
```

Expected output:

```text
A
  B
    E
    F
  C
  D
    G
    H
    I
children of A: 3, of D: 3
```

## Complexity

| Case | Cost |
| --- | --- |
| visit all nodes | O(n) |
| find the k-th child | O(k) |
| count the children of a node | O(degree) |

Space: O(n), exactly two pointers per node

A node with d children needs d pointers in the "array of children" design, but only 2 in left-child/right-sibling, whatever d is.

## Videos

- [Left Child Right Sibling Representation of N-ary Tree](https://youtu.be/O8rDi6a5R3g) (CSE Guru): Builds the left-child/right-sibling form of an n-ary tree step by step.
- [Convert general tree to binary tree](https://youtu.be/TE2-Zs2QTTw) (EZCSE): A 5-minute drill on converting a general tree to a binary tree, the usual exam question.

## Exam lens

Likely questions:

- What is a general tree? Why is a fixed number of child pointers a problem?
- Convert a drawn general tree into its left-child/right-sibling binary tree.
- Write the Node struct for the left-child/right-sibling representation.

Common mistakes:

- Linking a node's second child to the **parent** instead of to the first child's `nextSibling`.
- Drawing siblings as "right child of the parent".
- Forgetting that the root has no siblings.

## Quick check

1. In left-child/right-sibling, the `nextSibling` of node B points to…
   A. B's first child
   B. B's next brother (same parent)
   C. B's parent
   D. the root
   Answer: B. Children of one parent form a linked list through `nextSibling`.

2. A has children B, C, D. In the binary form, C is…
   A. A's left child
   B. B's right pointer (nextSibling)
   C. D's left child
   D. A's right child
   Answer: B. A → first child B; B → next sibling C; C → next sibling D.

3. How many pointers per node does this representation need?
   A. 1
   B. 2
   C. as many as the children
   D. log n
   Answer: B. firstChild and nextSibling.

## Practice

**Trace by hand.** General tree: R has children A, B, C. A has D, E. C has F. Write firstChild and nextSibling for every node.

Solution:

| node | firstChild | nextSibling |
| --- | --- | --- |
| R | A | – |
| A | D | B |
| B | – | C |
| C | F | – |
| D | – | E |
| E | – | – |
| F | – | – |


**Implement it.** Write `int height(GNode* n)` and `int countLeaves(GNode* n)` for the left-child/right-sibling tree.

Hint: Height: 1 + max over children (loop over `firstChild` → `nextSibling`). A leaf is a node with `firstChild == nullptr`.

**Problems:**

- [N-ary Tree Preorder Traversal](https://leetcode.com/problems/n-ary-tree-preorder-traversal/) (easy). Hint: Visit the node, then each child in order.
- [Maximum Depth of N-ary Tree](https://leetcode.com/problems/maximum-depth-of-n-ary-tree/) (easy). Hint: 1 + the max depth over all children.

## Mastery checklist

- [ ] I can explain what a general tree is.
- [ ] I can convert a general tree to left-child/right-sibling form.
- [ ] I can write the GNode struct and traverse it.