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

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

📖 Scenario: Imagine you are organizing a family tree. Each person is a node in the tree. You want to understand some basic terms used to describe the tree structure: root, leaf, height, depth, and level.

🎯 Goal: You will create a simple tree using a dictionary, identify the root and leaf nodes, calculate the height of the tree, and find the depth and level of specific nodes.

📋 What You'll Learn

Create a dictionary representing a simple tree structure

Define the root node

Identify leaf nodes

Calculate the height of the tree

Calculate the depth and level of given nodes

Print the results clearly

💡 Why This Matters

🌍 Real World

Trees are used to represent hierarchical data like family trees, file systems, and organizational charts.

💼 Career

Understanding tree terminology and traversal is essential for software developers working with data structures, databases, and UI components.

1

Create the tree structure

Create a dictionary called family_tree representing the tree with these exact entries: 'Grandparent': ['Parent1', 'Parent2'], 'Parent1': ['Child1', 'Child2'], 'Parent2': ['Child3'], 'Child1': [], 'Child2': [], 'Child3': []

DSA Python

# Your code here

Hint

Use a dictionary where keys are node names and values are lists of their children.

2

Define the root and find leaf nodes

Create a variable called root and set it to 'Grandparent'. Then create a list called leaf_nodes that contains all nodes from family_tree whose children list is empty.

DSA Python

family_tree = {
    'Grandparent': ['Parent1', 'Parent2'],
    'Parent1': ['Child1', 'Child2'],
    'Parent2': ['Child3'],
    'Child1': [],
    'Child2': [],
    'Child3': []
}
# Your code here

Hint

The root is the top node. Leaf nodes have no children, so their list is empty.

3

Calculate the height of the tree

Define a function called tree_height that takes a node name and returns the height of the tree from that node. Use recursion: if the node has no children, return 0; otherwise, return 1 plus the maximum height among its children. Then create a variable called height and set it to the height of the tree starting from root.

DSA Python

family_tree = {
    'Grandparent': ['Parent1', 'Parent2'],
    'Parent1': ['Child1', 'Child2'],
    'Parent2': ['Child3'],
    'Child1': [],
    'Child2': [],
    'Child3': []
}

root = 'Grandparent'
leaf_nodes = [node for node, children in family_tree.items() if children == []]

# Your code here

Hint

Use a recursive function that checks if a node has children. If none, height is 0; else 1 plus max height of children.

4

Calculate depth and level of nodes and print results

Define a function called node_depth that takes a node and a current_node (starting with root) and returns the depth of node. Depth is 0 for the root, and for others it is 1 plus the depth of its parent. Then print the following lines exactly: print(f"Root: {root}"), print(f"Leaf nodes: {leaf_nodes}"), print(f"Height of tree: {height}"), print(f"Depth of 'Child2': {node_depth('Child2', root)}"), and print(f"Level of 'Child2': {node_depth('Child2', root) + 1}").

DSA Python

family_tree = {
    'Grandparent': ['Parent1', 'Parent2'],
    'Parent1': ['Child1', 'Child2'],
    'Parent2': ['Child3'],
    'Child1': [],
    'Child2': [],
    'Child3': []
}

root = 'Grandparent'
leaf_nodes = [node for node, children in family_tree.items() if children == []]

def tree_height(node):
    if not family_tree[node]:
        return 0
    else:
        return 1 + max(tree_height(child) for child in family_tree[node])

height = tree_height(root)

# Your code here

Hint

Use recursion to find depth by checking children. Level is depth plus one. Print all results exactly as shown.

Practice

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

easy

A. A node at the lowest level

B. The topmost node with no parent

C. Any node with no children

D. A node with exactly two children

Solution

1. Step 1: Understand the root node definition

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

2. Step 2: Compare options with definition

   The topmost node with no parent matches this definition exactly. Other options describe leaf nodes or other properties.

3. Final Answer:

   The topmost node with no parent -> Option B

4. Quick Check:

   Root = topmost node with no parent [OK]

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

Common Mistakes:

• Confusing root with leaf node
• Thinking root has children always
• Mixing root with internal nodes

2. Which of the following is the correct way to represent the leaf node in a tree?

easy

A. A node with no children

B. A node with exactly one child

C. The root node

D. A node with at least one child

Solution

1. Step 1: Define leaf node

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

2. Step 2: Match definition with options

   A node with no children states a node with no children, which matches the leaf node definition.

3. Final Answer:

   A node with no children -> Option A

4. Quick Check:

   Leaf = node with no children [OK]

Hint: Leaf nodes have zero children [OK]

Common Mistakes:

• Thinking leaf nodes have children
• Confusing leaf with root
• Assuming leaf nodes must have one child

3. Consider the following tree structure:

       A
      / \
     B   C
    /   / \
   D   E   F

What is the height of node C?

medium

A. 0

B. 2

C. 3

D. 1

Solution

1. Step 1: Understand height of a node

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

2. Step 2: Calculate height of node C

   Node C has children E and F, both leaves with height 0. So height of C = 1 + max(0,0) = 1.

3. Step 3: Verify options

   1 says 1, but height counts edges down, so height is 1. 2 says 2, which is incorrect. 0 is 0, which is leaf height.

4. Final Answer:

   1 -> Option D

5. Quick Check:

   Height of C = 1 edge to leaf [OK]

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

Common Mistakes:

• Confusing height with depth
• Counting nodes instead of edges
• Assuming leaf height is 1

4. Given the tree below:

       X
      / \
     Y   Z
    / 
   W  

What is the depth of node W?
Note: Depth is the number of edges from the root to the node.

medium

A. 2

B. 1

C. 0

D. 3

Solution

1. Step 1: Understand depth definition

   Depth is the number of edges from the root node to the target node.

2. Step 2: Trace path from root to W

   Path: X (root) -> Y -> W. Number of edges = 2.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Depth of W = 2 edges from root [OK]

Hint: Count edges from root to node for depth [OK]

Common Mistakes:

• Counting nodes instead of edges
• Confusing depth with height
• Starting count from 1 instead of 0

5. In a tree, the level of a node is defined as its depth plus one. Given the tree:

        M
       / \
      N   O
     / \
    P   Q

What is the level of node Q?

hard

A. 1

B. 2

C. 3

D. 4

Solution

1. Step 1: Find depth of node Q

   Path from root M to Q is M -> N -> Q, which has 2 edges, so depth = 2.

2. Step 2: Calculate level using formula

   Level = depth + 1 = 2 + 1 = 3.

3. Final Answer:

   3 -> Option C

4. Quick Check:

   Level = depth + 1 = 3 [OK]

Hint: Level = depth + 1 always [OK]

Common Mistakes:

• Using depth as level directly
• Counting nodes incorrectly
• Confusing level with height