Tree Terminology Root Leaf Height Depth Level in DSA C# - Build from Scratch

Understanding Tree Terminology: Root, Leaf, Height, Depth, Level

📖 Scenario: Imagine a family tree where each person is connected to their children. We want to understand the basic parts of this tree: the root (the oldest ancestor), leaves (family members with no children), and how far each person is from the root (depth and level). We will also find the height of the tree, which tells us the longest path from the root to a leaf.

🎯 Goal: You will build a simple tree using nodes, identify the root and leaves, calculate the depth of each node, and find the height of the tree. Finally, you will print the tree nodes with their levels.

📋 What You'll Learn

Create a tree with nodes having integer values and child nodes

Identify the root node

Find all leaf nodes

Calculate the depth of each node starting from the root

Calculate the height of the tree

Print each node's value with its level

💡 Why This Matters

🌍 Real World

Trees are used in many areas like family trees, file systems, and organization charts. Understanding tree terms helps in navigating and managing these structures.

💼 Career

Knowing tree terminology and basic tree operations is essential for software developers, especially those working with data structures, databases, and algorithms.

1

Create the Tree Nodes

Create a class called TreeNode with an int property called Value and a list of TreeNode called Children. Then create the root node with value 1 and add two children with values 2 and 3. Add one child with value 4 to the node with value 2.

DSA C#

// Define TreeNode class and create the tree nodes
// Your code here

Hint

Start by defining the TreeNode class with a value and a list of children. Then create nodes and connect them as described.

2

Add a Method to Find Leaf Nodes

Add a method called GetLeaves that takes a TreeNode parameter and returns a list of all leaf nodes (nodes with no children). Use recursion to find leaves in the tree starting from the root.

DSA C#

using System;
using System.Collections.Generic;

class TreeNode
{
    public int Value;
    public List Children = new List();

    public TreeNode(int value)
    {
        Value = value;
    }
}

class Program
{
    static List GetLeaves(TreeNode node)
    {
        // Your code here
    }

    static void Main()
    {
        TreeNode root = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);

        root.Children.Add(node2);
        root.Children.Add(node3);
        node2.Children.Add(node4);
    }
}

Hint

Check if the node has no children, then it is a leaf. Otherwise, check all children recursively.

3

Calculate Height and Depth of Nodes

Add a method called GetHeight that takes a TreeNode and returns the height of the tree from that node. Also, add a method called PrintLevels that prints each node's value with its level (depth) starting from the root at level 0.

DSA C#

using System;
using System.Collections.Generic;

class TreeNode
{
    public int Value;
    public List Children = new List();

    public TreeNode(int value)
    {
        Value = value;
    }
}

class Program
{
    static List GetLeaves(TreeNode node)
    {
        List leaves = new List();
        if (node.Children.Count == 0)
        {
            leaves.Add(node);
        }
        else
        {
            foreach (TreeNode child in node.Children)
            {
                leaves.AddRange(GetLeaves(child));
            }
        }
        return leaves;
    }

    static int GetHeight(TreeNode node)
    {
        // Your code here
    }

    static void PrintLevels(TreeNode node, int level)
    {
        // Your code here
    }

    static void Main()
    {
        TreeNode root = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);

        root.Children.Add(node2);
        root.Children.Add(node3);
        node2.Children.Add(node4);
    }
}

Hint

Height is 0 for leaves. For other nodes, height is 1 plus the maximum height of children. For printing levels, print current node then call recursively for children with level + 1.

4

Print Leaves and Tree Height

In the Main method, call GetLeaves on the root and print each leaf node's value as Leaf: <value>. Then call GetHeight on the root and print the height as Height of tree: <height>. Finally, call PrintLevels on the root starting at level 0.

DSA C#

using System;
using System.Collections.Generic;

class TreeNode
{
    public int Value;
    public List Children = new List();

    public TreeNode(int value)
    {
        Value = value;
    }
}

class Program
{
    static List GetLeaves(TreeNode node)
    {
        List leaves = new List();
        if (node.Children.Count == 0)
        {
            leaves.Add(node);
        }
        else
        {
            foreach (TreeNode child in node.Children)
            {
                leaves.AddRange(GetLeaves(child));
            }
        }
        return leaves;
    }

    static int GetHeight(TreeNode node)
    {
        if (node.Children.Count == 0)
            return 0;

        int maxChildHeight = 0;
        foreach (TreeNode child in node.Children)
        {
            int childHeight = GetHeight(child);
            if (childHeight > maxChildHeight)
                maxChildHeight = childHeight;
        }
        return maxChildHeight + 1;
    }

    static void PrintLevels(TreeNode node, int level)
    {
        Console.WriteLine($"Node {node.Value} is at level {level}");
        foreach (TreeNode child in node.Children)
        {
            PrintLevels(child, level + 1);
        }
    }

    static void Main()
    {
        TreeNode root = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);

        root.Children.Add(node2);
        root.Children.Add(node3);
        node2.Children.Add(node4);

        // Print leaves, height, and levels
        // Your code here
    }
}

Hint

Use GetLeaves to get leaves and print them. Use GetHeight to get height and print it. Use PrintLevels starting at level 0 to print all nodes with their levels.

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