Tree Terminology Root Leaf Height Depth Level in DSA C++

Mental Model

A tree is a structure with a starting point called root, ends called leaves, and each node has a height and depth showing its position.

Analogy: Think of a family tree: the oldest ancestor is the root, youngest children with no kids are leaves, height is how far down the longest branch goes, and depth is how far a person is from the oldest ancestor.

        [Root]
         /   \
      [A]     [B]
     /   \       \
  [C]   [D]     [E]

Root = top node
Leaves = nodes with no children (C, D, E)
Height = longest path down (Root height = 2)
Depth = distance from root (Root depth = 0, A depth = 1)

Dry Run Walkthrough

Input: Tree with nodes: Root, A, B, C, D, E arranged as Root->A,B; A->C,D; B->E

Goal: Identify root, leaves, height of nodes, depth of nodes, and levels

Step 1: Identify the root node

[Root]
 /   \
[A]   [B]
/ \     \
[C][D]  [E]

Why: Root is the starting node with no parent

Step 2: Find leaf nodes (nodes with no children)

[Root]
 /   \
[A]   [B]
/ \     \
[C][D]  [E]
Leaves: C, D, E

Why: Leaves have no children, they end branches

Step 3: Calculate height of each node (longest path down to leaf)

Heights:
C=0, D=0, E=0
A=1 (max of C,D +1)
B=1 (E +1)
Root=2 (max of A,B +1)

Why: Height shows how far node is from bottom

Step 4: Calculate depth of each node (distance from root)

Depths:
Root=0
A=1, B=1
C=2, D=2, E=2

Why: Depth shows how far node is from top

Step 5: Assign levels based on depth

Levels:
Level 0: Root
Level 1: A, B
Level 2: C, D, E

Why: Levels group nodes by their depth

Result:

[Root]
 /   \
[A]   [B]
/ \     \
[C][D]  [E]
Root=depth0,height2
Leaves=C,D,E height0
Levels: 0->Root,1->A,B,2->C,D,E

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

struct Node {
    string val;
    vector<Node*> children;
    Node(string v) : val(v) {}
};

int height(Node* node) {
    if (!node) return -1; // empty node height
    if (node->children.empty()) return 0; // leaf height
    int maxChildHeight = -1;
    for (auto child : node->children) {
        int h = height(child); // get child's height
        if (h > maxChildHeight) maxChildHeight = h;
    }
    return maxChildHeight + 1; // height is max child's height + 1
}

void depthLevels(Node* root, vector<vector<string>>& levels) {
    if (!root) return;
    queue<pair<Node*, int>> q;
    q.push({root, 0});
    while (!q.empty()) {
        auto [node, d] = q.front(); q.pop();
        if (levels.size() == d) levels.push_back({});
        levels[d].push_back(node->val); // add node to its level
        for (auto child : node->children) {
            q.push({child, d + 1}); // enqueue children with depth+1
        }
    }
}

int main() {
    // Build tree
    Node* root = new Node("Root");
    Node* A = new Node("A");
    Node* B = new Node("B");
    Node* C = new Node("C");
    Node* D = new Node("D");
    Node* E = new Node("E");

    root->children = {A, B};
    A->children = {C, D};
    B->children = {E};

    // Print root
    cout << "Root: " << root->val << "\n";

    // Find leaves
    vector<Node*> leaves;
    vector<Node*> stack = {root};
    while (!stack.empty()) {
        Node* curr = stack.back(); stack.pop_back();
        if (curr->children.empty()) leaves.push_back(curr);
        else {
            for (auto child : curr->children) stack.push_back(child);
        }
    }
    cout << "Leaves: ";
    for (auto leaf : leaves) cout << leaf->val << " ";
    cout << "\n";

    // Heights
    cout << "Heights:\n";
    cout << "C=" << height(C) << ", D=" << height(D) << ", E=" << height(E) << "\n";
    cout << "A=" << height(A) << ", B=" << height(B) << ", Root=" << height(root) << "\n";

    // Depths and levels
    vector<vector<string>> levels;
    depthLevels(root, levels);
    cout << "Levels by depth:\n";
    for (int i = 0; i < (int)levels.size(); i++) {
        cout << "Level " << i << ": ";
        for (auto val : levels[i]) cout << val << " ";
        cout << "\n";
    }

    return 0;
}

if (!node) return -1; // empty node height

handle empty node base case

if (node->children.empty()) return 0; // leaf height

leaf nodes have height 0

for (auto child : node->children) { int h = height(child); if (h > maxChildHeight) maxChildHeight = h; }

compute max height among children

return maxChildHeight + 1; // height is max child's height + 1

height includes current node

q.push({root, 0});

start BFS with root at depth 0

levels[d].push_back(node->val);

add node to its depth level

for (auto child : node->children) q.push({child, d + 1});

enqueue children with depth incremented

if (curr->children.empty()) leaves.push_back(curr);

collect leaves during traversal

Output

Root: Root

Leaves: C D E 

Heights:

C=0, D=0, E=0

A=1, B=1, Root=2

Levels by depth:

Level 0: Root 

Level 1: A B 

Level 2: C D E 

Complexity Analysis

Time: O(n) because we visit each node once to compute height and depth

Space: O(n) for recursion stack and queue storing nodes at each level

vs Alternative: Compared to repeated searches, this single traversal approach is efficient and avoids redundant work

Edge Cases

Empty tree (root is null)

Height returns -1, no levels or leaves found

DSA C++

if (!node) return -1; // empty node height

Single node tree (only root)

Root is also leaf, height 0, depth 0, level 0

DSA C++

if (node->children.empty()) return 0; // leaf height

When to Use This Pattern

When a problem involves hierarchical data or parent-child relationships, recognize tree terminology to understand node positions and relationships.

Common Mistakes

Mistake: Confusing height with depth by mixing their definitions
Fix: Remember height is distance down to leaves, depth is distance up from root

Mistake: Counting root as leaf or vice versa
Fix: Check if node has children to decide leaf status

Summary

Defines key tree terms: root is start, leaves are ends, height is longest path down, depth is distance from root, levels group nodes by depth.

Use when you need to understand or explain positions of nodes in a tree structure.

Height measures distance to bottom, depth measures distance from top; this difference is the key to understanding tree layout.