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.
Rule of this site: Don't just watch: implement it yourself, then solve 2–3 problems.
02Mental 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:
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.
03Visualize
space play · ←→ step · r reset. The highlighted code line follows each step.
Watch each node keep a pointer to its first child, and each child point to its next sibling.
04C++ code
Compiled and run with g++ -std=c++17; the output below is real. Type it out yourself before you copy it.
#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);
}A
B
E
F
C
D
G
H
I
children of A: 3, of D: 305Complexity
| visit all nodes | O(n) |
|---|---|
| find the k-th child | O(k) |
| count the children of a node | O(degree) |
| Extra 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.
06Watch
Left Child Right Sibling Representation of N-ary Tree
Why this one: Builds the left-child/right-sibling form of an n-ary tree step by step.
Convert general tree to binary tree
Why this one: A 5-minute drill on converting a general tree to a binary tree, the usual exam question.
07Exam 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.
08Quick check
09Practice
🟢 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.
Show answer
| 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.
🔴 Solve problems
Hint
Visit the node, then each child in order.
Hint
1 + the max depth over all children.
10Mastery checklist
Tick these honestly. When every box is ticked, the topic is marked complete.