Tree Terminology Root Leaf Height Depth Level in DSA C#

Mental Model

A tree is a structure with nodes connected like branches, starting from one main node called root, ending at nodes called leaves. Height, depth, and level tell us how far nodes are from root or leaves.

Analogy: Think of a family tree: the oldest ancestor is the root, youngest children with no kids are leaves, height is how tall the family tree is, depth is how far a person is from the oldest ancestor, and level is the generation number.

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

Root = top node
Leaves = nodes with no children (C, D, F)
Height = longest path from root to leaf
Depth = distance from root to node
Level = depth + 1

Dry Run Walkthrough

Input: Tree with nodes: Root has children A and B; A has children C and D; B has child E; E has child F

Goal: Identify root, leaves, height, depth, and level of each node

Step 1: Identify the root node

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

Why: Root is the top node with no parent

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

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

Leaves: C, D, F

Why: Leaves have no children, they end branches

Step 3: Calculate height of tree (longest path from root to leaf)

Longest path: Root -> B -> E -> F
Height = 3

Why: Height shows how tall the tree is from root down

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

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

Why: Depth tells how far a node is from root

Step 5: Calculate level of each node (depth + 1)

Levels:
Root=1
A=2, B=2
C=3, D=3, E=3
F=4

Why: Level counts generations starting at 1 for root

Result:

[Root (level 1, depth 0)]
 /           \
[A (2,1)]    [B (2,1)]
 /     \          \
[C (3,2)][D (3,2)] [E (3,2)]
                        \
                        [F (4,3)]

Leaves: C, D, F
Height: 3

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class TreeNode
{
    public string Value;
    public List<TreeNode> Children = new List<TreeNode>();
    public TreeNode(string val) { Value = val; }
}

class TreeTerminology
{
    public TreeNode Root;

    public TreeTerminology(TreeNode root) { Root = root; }

    public List<TreeNode> GetLeaves(TreeNode node)
    {
        var leaves = new List<TreeNode>();
        if (node == null) return leaves; // guard for null node
        if (node.Children.Count == 0) // leaf check
            leaves.Add(node);
        else
            foreach (var child in node.Children)
                leaves.AddRange(GetLeaves(child));
        return leaves;
    }

    public int GetHeight(TreeNode node)
    {
        if (node == null) return -1; // guard for null node
        if (node.Children.Count == 0) // leaf node height 0
            return 0;
        int maxChildHeight = 0;
        foreach (var child in node.Children)
        {
            int childHeight = GetHeight(child); // recursive height
            if (childHeight > maxChildHeight)
                maxChildHeight = childHeight;
        }
        return maxChildHeight + 1; // add edge to child
    }

    public void PrintDepthAndLevel(TreeNode node, int depth)
    {
        if (node == null) return; // guard for null node
        Console.WriteLine($"Node {node.Value}: Depth={depth}, Level={depth + 1}");
        foreach (var child in node.Children)
            PrintDepthAndLevel(child, depth + 1); // depth increases down tree
    }

    public static void Main()
    {
        var root = new TreeNode("Root");
        var A = new TreeNode("A");
        var B = new TreeNode("B");
        var C = new TreeNode("C");
        var D = new TreeNode("D");
        var E = new TreeNode("E");
        var F = new TreeNode("F");

        root.Children.Add(A);
        root.Children.Add(B);
        A.Children.Add(C);
        A.Children.Add(D);
        B.Children.Add(E);
        E.Children.Add(F);

        var tree = new TreeTerminology(root);

        var leaves = tree.GetLeaves(root);
        Console.Write("Leaves: ");
        foreach (var leaf in leaves)
            Console.Write(leaf.Value + " ");
        Console.WriteLine();

        int height = tree.GetHeight(root);
        Console.WriteLine("Height: " + height);

        tree.PrintDepthAndLevel(root, 0);
    }
}

if (node.Children.Count == 0) // leaf check

detect leaf nodes with no children

int childHeight = GetHeight(child); // recursive height

calculate height of each child subtree

return maxChildHeight + 1; // add edge to child

height is max child height plus one edge

Console.WriteLine($"Node {node.Value}: Depth={depth}, Level={depth + 1}");

print depth and level for current node

PrintDepthAndLevel(child, depth + 1); // depth increases down tree

recurse to children increasing depth

Output

Leaves: C D F 

Height: 3

Node Root: Depth=0, Level=1

Node A: Depth=1, Level=2

Node C: Depth=2, Level=3

Node D: Depth=2, Level=3

Node B: Depth=1, Level=2

Node E: Depth=2, Level=3

Node F: Depth=3, Level=4

Complexity Analysis

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

Space: O(h) where h is tree height due to recursion stack during traversal

vs Alternative: Compared to iterative BFS for depth/level, recursion is simpler but uses call stack; BFS uses queue but same O(n) time

Edge Cases

Empty tree (root is null)

No nodes to process; leaves list empty, height -1, no depth/level printed

DSA C#

var leaves = tree.GetLeaves(root); // root null would cause no calls

Single node tree (only root)

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

DSA C#

if (node.Children.Count == 0) // leaf check

Tree with multiple leaves at different depths

Leaves correctly identified; height is longest path; depths and levels correct per node

DSA C#

int childHeight = GetHeight(child); // recursive height

When to Use This Pattern

When a problem asks about parts of a tree like root, leaves, height, depth, or level, use tree traversal and simple definitions to identify these properties.

Common Mistakes

Mistake: Confusing depth and height or mixing their definitions
Fix: Remember depth is distance from root down; height is longest distance from node down to leaf

Mistake: Counting level starting at 0 instead of 1
Fix: Level is depth plus one, so root is level 1

Summary

Defines key parts of a tree: root, leaves, height, depth, and level.

Use when understanding or explaining tree structure and node positions.

Height measures longest path down; depth measures distance from root; level is depth plus one.

Practice

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

easy

A. The topmost node with no parent

B. A node with no children

C. Any node at the bottom level

D. A node with exactly two children

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: Identify the correct description

   Among the options, only the topmost node with no parent matches the root node definition.

3. Final Answer:

   The topmost node with no parent -> Option A

4. Quick Check:

   Root = topmost node with no parent [OK]

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

Common Mistakes:

• Confusing root with leaf nodes
• Thinking root must have children
• Assuming root is any node at the bottom

2. Which of the following is the correct way to declare a simple tree node class in C# with a value and children list?

easy

A. class Node { int Value; int Children; }

B. class Node { public int Value; public Node Children; }

C. class Node { public int Value; public List<Node> Children; }

D. class Node { public int Value; public Node[] Children; }

Solution

1. Step 1: Check for correct data types and access modifiers

   The node should have a public integer value and a list of child nodes. class Node { public int Value; public List<Node> Children; } uses List<Node> which is correct.

2. Step 2: Eliminate incorrect options

   class Node { int Value; int Children; } uses int for children which is wrong. class Node { public int Value; public Node Children; } uses a single Node for children instead of a list. class Node { public int Value; public Node[] Children; } uses an array which is valid but less flexible than List.

3. Final Answer:

   class Node { public int Value; public List<Node> Children; } -> Option C

4. Quick Check:

   Use List<Node> for children in C# [OK]

Hint: Use List<Node> for multiple children in C# [OK]

Common Mistakes:

• Using int instead of List<Node> for children
• Missing public access modifier
• Using single Node instead of collection for children

3. Given a tree where the root is at level 0, what is the level of a leaf node that is 4 edges away from the root?

easy

A. 3

B. 4

C. 5

D. 6

Solution

1. Step 1: Understand level definition

   Level of a node is the number of edges from the root to that node, starting at 0 for root.

2. Step 2: Calculate leaf node level

   If leaf is 4 edges away from root, its level is 4.

3. Final Answer:

   4 -> Option B

4. Quick Check:

   Level = edges from root = 4 [OK]

Hint: Level equals number of edges from root [OK]

Common Mistakes:

• Confusing level with height
• Starting level count at 1 instead of 0
• Mixing depth and level definitions

4. Consider the following tree structure:

Node root = new Node { Value = 1, Children = new List<Node> {
  new Node { Value = 2, Children = new List<Node> {
    new Node { Value = 4, Children = new List<Node>() },
    new Node { Value = 5, Children = new List<Node>() }
  }},
  new Node { Value = 3, Children = new List<Node>() }
}};

What is the height of this tree?

medium

A. 2

B. 3

C. 1

D. 4

Solution

1. Step 1: Understand height definition

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

2. Step 2: Trace the longest path in the tree

   Longest path: root(1) -> 2 -> 4 (or 5). This path has 2 edges, so height = 2.

3. Step 3: Reconsider height counting

   Height is often defined as the number of nodes on the longest path minus 1, which equals the number of edges. The path has 3 nodes (1,2,4), so height = 2 edges, which is correct. However, some definitions count height as number of nodes, which would be 3.

4. Step 4: Confirm standard definition

   Standard definition: height = number of edges = 2.

5. Final Answer:

   2 -> Option A

6. Quick Check:

   Height = longest path edges = 2 [OK]

Hint: Height = number of edges on longest root-to-leaf path [OK]

Common Mistakes:

• Counting nodes instead of edges for height
• Confusing height with depth
• Ignoring leaf nodes at bottom

5. The following code tries to calculate the depth of a node in a tree but has a bug:

int GetDepth(Node node) {
  if (node == null) return 0;
  return 1 + GetDepth(node.Children[0]);
}

What is the main problem with this code?

medium

A. It causes infinite recursion for leaf nodes

B. It returns 0 for null nodes instead of -1

C. It does not handle the root node correctly

D. It only checks the first child, ignoring others

Solution

1. Step 1: Analyze recursion logic

   The function calls itself only on the first child (Children[0]), ignoring other children.

2. Step 2: Identify the bug impact

   This means it does not calculate depth correctly if node has multiple children; it misses deeper paths.

3. Final Answer:

   It only checks the first child, ignoring others -> Option D

4. Quick Check:

   Check all children for correct depth [OK]

Hint: Check all children, not just first, when calculating depth [OK]

Common Mistakes:

• Assuming single child trees only
• Ignoring null checks for children list
• Confusing depth with height