Introduction to Trees

So far you have seen data stored in a straight line. Arrays, linked lists, stacks, queues. One item, then the next, then the next. But not all data lives in a line. Some data is shaped like a family. One thing owns many things below it. That is where trees come in.

🌳 The Problem: Some Data Is Not Flat

Think about the folders on your computer. You open Documents, and inside it there are more folders. Inside those, even more folders. And then finally some files. A folder can hold many folders. Each of those can hold many more.

Now try to store that in a plain list:

Documents, Photos, Resume.pdf, Trip2024, Beach.jpg, Mountains.jpg, Work, Report.docx

See the problem? The list shows the names. But it loses the shape. You cannot tell that Beach.jpg lives inside Trip2024, which lives inside Photos. A flat list has no idea who is inside whom. The relationship is gone.

This kind of data is hierarchical. That means items are arranged in levels. One item sits above and owns the items below it. A list cannot show levels. A tree can.

📚 What Is a Tree?

A tree is a data structure that stores data in nodes connected in a hierarchy. A node is just one box that holds a value. The tree starts from one top node and spreads downward into more nodes, like branches.

Here is the key idea. There is one node at the very top. Every other node sits below some other node. Nothing floats on its own. So the whole thing stays connected and organised, from the top going down.

Quick way to picture it:

• one box at the top
• that box points down to a few more boxes
• each of those can point down to even more
• it keeps branching until you reach boxes with nothing below them

A real family tree works the same way. One grandparent at the top. Their children below. Then grandchildren below that.

🔑 The Words You Need: Root, Parent, Child, Leaf

A tree has a few simple names for its parts. Let us define each one in plain words.

• Root — the single node at the very top. It has nothing above it. Every tree has exactly one root.
• Parent — a node that has one or more nodes directly below it. The node above is the parent of the nodes below.
• Child — a node that sits directly below another node. That node below is the child. One parent can have many children.
• Leaf — a node with no children. It is the end of a branch. Nothing hangs below a leaf.

The root is where everything begins. From the root you walk down to children, then their children, until you hit the leaves at the bottom.

One small note. A node can be a parent and a child at the same time. A middle folder has a folder above it, so it is a child. And it has folders inside it, so it is a parent. Only the root is never a child. And only a leaf is never a parent.

🗂️ A Tree You Can See

Let us draw that folder example as a real tree. Read it from the top down.

Now the shape is clear. Documents is the root. Photos is a child of Documents and also a parent of Trip2024. Beach.jpg and Mountains.jpg are leaves because nothing lives inside them.

Walk through it once:

• Documents is the root. Nothing is above it.
• Photos and Resume.pdf are children of Documents.
• Trip2024 is a child of Photos, and a parent of the two images.
• Beach.jpg, Mountains.jpg, and Resume.pdf are leaves.

🌍 Where Trees Show Up in Real Life

Trees are not just a textbook idea. You use them every day without noticing.

• File system — folders inside folders, exactly like the example above. Your phone and laptop both store files as a tree.
• Company org chart — the CEO sits at the top. Managers report to the CEO. Team members report to managers. That is a tree, and the CEO is the root.
• HTML page structure — every web page is a tree. The html tag is the root. Inside it sit head and body. Inside body sit headings, paragraphs, images. The browser actually builds this tree to draw the page.

Notice the pattern in all of these. One thing at the top, and a clear “who is inside whom” going down. Whenever your data has that shape, a tree is the natural way to store it.

💻 What One Node Looks Like in Code

You do not need heavy code to understand trees yet. But it helps to see what a single node is made of. A node holds a value, and it holds links to its children.

Here we make one node that stores a value and keeps a list of its children. Then we attach two children to it and print them.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// A node holds a value and pointers to its children.
#define MAX_CHILDREN 10

typedef struct Node {
    char value[20];
    struct Node *children[MAX_CHILDREN];
    int childCount;
} Node;

// Make a new node with the given value.
Node *makeNode(const char *value) {
    Node *n = (Node *)malloc(sizeof(Node));
    strcpy(n->value, value);
    n->childCount = 0;
    return n;
}

// Attach a child under a parent node.
void addChild(Node *parent, Node *child) {
    parent->children[parent->childCount] = child;
    parent->childCount++;
}

int main(void) {
    Node *root = makeNode("Documents");
    addChild(root, makeNode("Photos"));
    addChild(root, makeNode("Resume.pdf"));

    printf("Root: %s\n", root->value);
    for (int i = 0; i < root->childCount; i++) {
        printf("Child: %s\n", root->children[i]->value);
    }
    // A real program would call free() on each node here.
    return 0;
}

Root: Documents
Child: Photos
Child: Resume.pdf

#include <iostream>
#include <string>
#include <vector>
using namespace std;

// A node holds a value and a list of its children.
struct Node {
    string value;
    vector<Node *> children;
    Node(string v) : value(v) {}
};

// Attach a child under a parent node.
void addChild(Node *parent, Node *child) {
    parent->children.push_back(child);
}

int main() {
    Node *root = new Node("Documents");
    addChild(root, new Node("Photos"));
    addChild(root, new Node("Resume.pdf"));

    cout << "Root: " << root->value << endl;
    for (Node *child : root->children) {
        cout << "Child: " << child->value << endl;
    }
    return 0;
}

Root: Documents
Child: Photos
Child: Resume.pdf

import java.util.ArrayList;
import java.util.List;

public class TreeNode {
    // A node holds a value and a list of its children.
    static class Node {
        String value;
        List<Node> children = new ArrayList<>();
        Node(String value) {
            this.value = value;
        }
    }

    // Attach a child under a parent node.
    static void addChild(Node parent, Node child) {
        parent.children.add(child);
    }

    public static void main(String[] args) {
        Node root = new Node("Documents");
        addChild(root, new Node("Photos"));
        addChild(root, new Node("Resume.pdf"));

        System.out.println("Root: " + root.value);
        for (Node child : root.children) {
            System.out.println("Child: " + child.value);
        }
    }
}

Root: Documents
Child: Photos
Child: Resume.pdf

# A node holds a value and a list of its children.
class Node:
    def __init__(self, value):
        self.value = value
        self.children = []

# Attach a child under a parent node.
def add_child(parent, child):
    parent.children.append(child)

root = Node("Documents")
add_child(root, Node("Photos"))
add_child(root, Node("Resume.pdf"))

print("Root:", root.value)
for child in root.children:
    print("Child:", child.value)

Root: Documents
Child: Photos
Child: Resume.pdf

// A node holds a value and a list of its children.
class Node {
  constructor(value) {
    this.value = value;
    this.children = [];
  }
}

// Attach a child under a parent node.
function addChild(parent, child) {
  parent.children.push(child);
}

const root = new Node("Documents");
addChild(root, new Node("Photos"));
addChild(root, new Node("Resume.pdf"));

console.log("Root:", root.value);
for (const child of root.children) {
  console.log("Child:", child.value);
}

Root: Documents
Child: Photos
Child: Resume.pdf

See how small that is? A node is just a value plus a way to reach its children. Stack many of these together and you have a tree.

⚠️ Common Mistakes Beginners Make

A few things trip people up when they first meet trees. Keep these in mind.

• Thinking a tree can have many roots. It cannot. A tree has exactly one root at the top.
• Mixing up leaf and root. The root is at the top with nothing above it. A leaf is at the bottom with nothing below it.
• Forgetting that one node can be both a parent and a child. A middle node is a child of the node above and a parent of the nodes below.
• Drawing the root at the bottom. In computer science the root goes on top and the tree grows downward.
• Connecting a child to two parents. In a tree, each node has only one parent (except the root, which has none).

🧩 What You’ve Learned

• ✅ A tree stores data in a hierarchy of nodes, not in a flat line.
• ✅ It is the natural fit for data where one item owns many items below it.
• ✅ The root is the single top node, and every other node sits below it.
• ✅ A parent has nodes below it, a child sits below a parent, and a leaf has no children.
• ✅ One node can be both a parent and a child at the same time.
• ✅ File systems, org charts, and HTML pages are all real trees.
• ✅ A node in code is just a value plus links to its children.

🚀 What’s Next?

• Tree Terminology
• Binary Tree