Unit 2 · Lesson 218 minAcademic review pending

Two ways to hold a tree in memory

A tree can live in an array using index arithmetic, or in linked nodes like Unit I's lists. And a clever pointer trick lets the same left/right shape represent a general tree with any number of children.

Choose explanation

After this lesson

You should be able to

Declare a binary tree node with left and right pointers.
Compute a node's children positions in an array representation.
Encode a general tree as a binary tree using left-child, right-sibling.

Linked nodes: the default from here on

A binary tree node is a struct with a value and two pointers, exactly like Unit I's doubly linked list except the two pointers mean left child and right child instead of previous and next. This is the representation the rest of this unit uses.

One struct, two directions

struct Node {
    int data;
    struct Node *left;
    struct Node *right;
};

Array representation, and where it comes from

A binary tree can also live in a plain array, with no pointers at all. Put the root at index 0. For any node at index i, its left child sits at 2i + 1 and its right child at 2i + 2. No node stores an address; the shape is implied entirely by position.

This only works well when the tree is nearly full — a mostly-empty tree wastes huge stretches of array on gaps. That trade-off is exactly why Unit III's heaps, which are always kept full and balanced by construction, use array representation, while the BST you build for the rest of this unit uses linked nodes.

Encoding a general tree: left-child, right-sibling

The same two-pointer struct can represent a general tree, with a reinterpretation: left points to the node's first child, and right points to its next sibling — not to a second child at all. A manager with three reports becomes: left points to report one; report one's right points to report two; report two's right points to report three.

This is a genuinely clever reuse: the exact same struct definition, walked with a different mental model, turns an unlimited-children tree into a two-pointer binary shape — which is why every tree algorithm you learn for binary trees this unit generalizes.

Same struct, reinterpreted: left = first child, right = next sibling

/* VP-Eng has three reports: Dev-1, Dev-2, Dev-3 */

struct Node vp     = {"VP-Eng", &dev1, NULL};
struct Node dev1    = {"Dev-1",  NULL,  &dev2};  /* left: n/a, right: next sibling */
struct Node dev2    = {"Dev-2",  NULL,  &dev3};
struct Node dev3    = {"Dev-3",  NULL,  NULL};

/* vp.left is "first child" (Dev-1); dev1.right is "next sibling" (Dev-2) */

Try it yourself

A folder has three subfolders: Photos, Music, Docs. Photos itself contains two subfolders: 2024, 2025. Draw this as a left-child/right-sibling binary encoding and write the struct literals for it.

Need a hint?

Photos, being the first child of the folder, needs its own left pointer for its own first child — the encoding applies at every level, not just the top.

Check the worked solution

Photos needs both a left (its own first child, 2024) and a right (its sibling, Music) — the encoding is recursive, the same rule applied at every node, which is exactly why one struct definition covers a folder tree of any depth.

struct Node folder = {"root",  &photos, NULL};
struct Node photos = {"Photos", &y2024,  &music};
struct Node y2024   = {"2024",   NULL,    &y2025};
struct Node y2025   = {"2025",   NULL,    NULL};
struct Node music  = {"Music",  NULL,    &docs};
struct Node docs   = {"Docs",   NULL,    NULL};

Quick check

In a left-child, right-sibling encoding, what does a node's right pointer mean?

Select an answer to check your thinking.

Why this lesson exists

Syllabus mapping

creating a Binary Tree from a General Tree

Maps to course outcomes CO1, CO4.