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.

Practice

1. In a tree data structure, which node is called the root?

easy

A. A node with exactly two children

B. A node with no children

C. The topmost node with no parent

D. Any node at the bottom level

Solution

1. Step 1: Understand the root node concept

   The root node is the starting point of a tree and has no parent node above it.

2. Step 2: Differentiate root from other nodes

   Leaf nodes have no children, but root has no parent. Bottom level nodes are leaves or internal nodes, not necessarily root.

3. Final Answer:

   The topmost node with no parent -> Option C

4. Quick Check:

   Root = topmost node with no parent [OK]

Hint: Root is the only node without a parent [OK]

Common Mistakes:

• Confusing root with leaf node
• Thinking root must have children
• Assuming root is at bottom level

2. Which of the following is the correct way to declare a simple binary tree node struct in C++?

easy

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

B. struct Node { int data; Node left; Node right; };

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

D. struct Node { int data; int left; int right; };

Solution

1. Step 1: Check pointer usage for child nodes

   Child nodes must be pointers to Node to allow recursive structure.

2. Step 2: Validate data types of members

   Data is int, left and right are pointers to Node, so struct Node { int data; Node* left; Node* right; }; is correct.

3. Final Answer:

   struct Node { int data; Node* left; Node* right; }; -> Option A

4. Quick Check:

   Child nodes use pointers in struct [OK]

Hint: Child nodes must be pointers to Node type [OK]

Common Mistakes:

• Using Node instead of Node* for children
• Mixing int and Node types for children
• Missing semicolon at struct end

3. Consider the following tree:

        10
       /  \
      5    15
     /    /  \
    3    12  20

What is the height of the node with value 5?

medium

A. 1

B. 2

C. 3

D. 0

Solution

1. Step 1: Understand height definition

   Height of a node is the number of edges on the longest path from that node down to a leaf.

2. Step 2: Calculate height of node 5

   Node 5 has left child 3 (leaf). Longest path from 5 to leaf is 5 -> 3, which is 1 edge. Height of 3 is 0. Height of 5 = 1 + max height of children = 1 + 0 = 1. However, node 5 has no right child, so max height is 1. So height is 1. But the question asks for height of node 5. Since 3 is leaf (height 0), height of 5 is 1. But 2 says 2, which is incorrect. So correct answer is 1 (1).

3. Final Answer:

   1 -> Option A

4. Quick Check:

   Height = edges to deepest leaf = 1 [OK]

Hint: Height counts edges down to deepest leaf [OK]

Common Mistakes:

• Counting nodes instead of edges
• Confusing height with depth
• Ignoring missing right child

4. Given the following code snippet, what is the error?

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

Node* root = new Node{10, nullptr, nullptr};
root->left = new Node{5, nullptr, nullptr};
root->left->left = new Node{3, nullptr, nullptr};
root->right = new Node{15, nullptr, nullptr};
root->right->right = new Node{20, nullptr, nullptr};
root->right->left = 12;

medium

A. Incorrect initialization of root node

B. Missing semicolon after struct definition

C. Using nullptr instead of NULL

D. Assigning int 12 to a Node* pointer

Solution

1. Step 1: Analyze the last assignment

   Line root->right->left = 12; assigns integer 12 to a pointer Node* left, which is invalid.

2. Step 2: Check pointer assignment rules

   Pointers must be assigned addresses or nullptr, not raw integers.

3. Final Answer:

   Assigning int 12 to a Node* pointer -> Option D

4. Quick Check:

   Pointer must hold address, not int [OK]

Hint: Pointers cannot hold raw integers [OK]

Common Mistakes:

• Ignoring type mismatch in assignment
• Thinking nullptr and NULL difference causes error
• Overlooking semicolon presence

5. In a tree, the depth of a node is defined as the number of edges from the root to that node. Given the tree:

        1
       / \
      2   3
     /   / \
    4   5   6
       /
      7

What is the depth of node 7 and what is its level?

hard

A. Depth = 3, Level = 3

B. Depth = 3, Level = 4

C. Depth = 4, Level = 3

D. Depth = 4, Level = 4

Solution

1. Step 1: Calculate depth of node 7

   Path from root (1) to 7 is 1 -> 3 -> 5 -> 7, which has 3 edges, so depth = 3.

2. Step 2: Calculate level of node 7

   Level is depth + 1, so level = 3 + 1 = 4.

3. Final Answer:

   Depth = 3, Level = 4 -> Option B

4. Quick Check:

   Level = depth + 1 = 4 [OK]

Hint: Level = depth + 1 always [OK]

Common Mistakes:

• Confusing depth with level
• Counting nodes instead of edges for depth
• Starting depth count from 0 or 1 incorrectly