Tree Terminology Root Leaf Height Depth Level in DSA C# - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the root of a tree?

The root is the topmost node of a tree. It has no parent and is the starting point of the tree.

beginner

Define a leaf node in a tree.

A leaf node is a node that has no children. It is at the end of a branch.

intermediate

What does the height of a node represent in a tree?

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

intermediate

Explain the depth of a node in a tree.

Depth of a node is the number of edges from the root node down to that node.

beginner

What is the level of a node in a tree?

Level of a node is its depth plus one. The root is at level 1, its children at level 2, and so on.

Which node in a tree has no parent?

A Child

B Leaf

C Root

D Sibling

The root node is the only node without a parent.

A node with no children is called?

A Root

B Parent

C Internal node

D Leaf

Leaf nodes have no children.

What is the height of a leaf node?

A Same as depth

B 0

C Depends on tree

D 1

Leaf nodes have height 0 because there are no edges below them.

Depth of the root node is?

A 0

B 1

C Depends on tree

D Height of tree

Root node is at depth 0 because there are no edges above it.

If a node is at depth 3, what is its level?

A 4

B 3

C 2

D 5

Level = depth + 1, so level is 4.

Describe the difference between height and depth of a node in a tree.

Think about where you start counting from for each.

Explain what the level of a node means and how it relates to depth.

Level starts counting nodes, depth counts edges.

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