Bird
Raised Fist0
DSA Pythonprogramming

Tree Terminology Root Leaf Height Depth Level in DSA Python

Choose your learning style10 modes available
LearnWhyDeepVisualTryChallengeProjectRecallTime
Mental Model
A tree is a structure with a starting point called root, ends called leaves, and measures like height and depth 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 many generations from oldest to youngest, depth is how far a person is from the oldest ancestor, and level groups people by generation.
       [Root]
       /    \
   [Node]  [Node]
    /          \
[Leaf]       [Leaf]

Root = top node
Leaves = nodes with no children
Height = longest path down
Depth = distance from root
Level = nodes at same depth
Dry Run Walkthrough
Input: Tree with root 1, children 2 and 3; node 2 has child 4; nodes 3 and 4 are leaves
Goal: Identify root, leaves, height, depth, and level of each node
Step 1: Identify root node
1 (root)
├─ 2
│  └─ 4
└─ 3
Why: Root is the starting point of the tree
Step 2: Find leaves (nodes with no children)
Leaves: 3, 4
Why: Leaves have no children, they end branches
Step 3: Calculate depth of each node from root
Depths: 1=0, 2=1, 3=1, 4=2
Why: Depth shows how far each node is from root
Step 4: Calculate height of tree (max depth of leaves)
Height = 2 (from root 1 to leaf 4)
Why: Height is longest path from root to any leaf
Step 5: Group nodes by level (nodes with same depth)
Level 0: 1
Level 1: 2, 3
Level 2: 4
Why: Level groups nodes by their distance from root
Result: 
Root: 1
Leaves: 3, 4
Height: 2
Depths: 1=0, 2=1, 3=1, 4=2
Levels:
  Level 0: 1
  Level 1: 2, 3
  Level 2: 4
Annotated Code
DSA Python
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.children = []

def find_root(nodes):
    # Root is node not child of any
    all_nodes = set(nodes)
    child_nodes = set(c for node in nodes for c in node.children)
    roots = all_nodes - child_nodes
    return roots.pop() if roots else None

def find_leaves(nodes):
    # Leaves have no children
    return [node for node in nodes if not node.children]

def calculate_depths(root):
    depths = {}
    def dfs(node, depth):
        depths[node.val] = depth
        for child in node.children:
            dfs(child, depth + 1)
    dfs(root, 0)
    return depths

def calculate_height(root):
    if not root.children:
        return 0
    return 1 + max(calculate_height(child) for child in root.children)

def group_by_level(depths):
    levels = {}
    for node_val, depth in depths.items():
        levels.setdefault(depth, []).append(node_val)
    return levels

# Build tree nodes
node1 = TreeNode(1)
node2 = TreeNode(2)
node3 = TreeNode(3)
node4 = TreeNode(4)

# Connect nodes
node1.children = [node2, node3]
node2.children = [node4]

nodes = [node1, node2, node3, node4]

root = find_root(nodes)
leaves = find_leaves(nodes)
depths = calculate_depths(root)
height = calculate_height(root)
levels = group_by_level(depths)

print(f"Root: {root.val}")
print("Leaves:", ", ".join(str(n.val) for n in leaves))
print(f"Height: {height}")
print("Depths:", ", ".join(f"{k}={v}" for k,v in sorted(depths.items())))
print("Levels:")
for level in sorted(levels):
    print(f"  Level {level}: {', '.join(str(n) for n in sorted(levels[level]))}")
roots = all_nodes - child_nodes
find node that is not child of any node -- identifies root
return [node for node in nodes if not node.children]
collect nodes with no children -- these are leaves
depths[node.val] = depth
record depth of current node during DFS traversal
return 1 + max(calculate_height(child) for child in root.children)
height is 1 plus max height among children
levels.setdefault(depth, []).append(node_val)
group nodes by their depth into levels
OutputSuccess
Root: 1 Leaves: 3, 4 Height: 2 Depths: 1=0, 2=1, 3=1, 4=2 Levels: Level 0: 1 Level 1: 2, 3 Level 2: 4
Complexity Analysis
Time: O(n) because we visit each node once for depth, height, and leaf calculations
Space: O(n) for storing nodes, depths, and levels
vs Alternative: Compared to repeated searches for root or leaves, this approach uses sets and DFS once, making it efficient
Edge Cases
Single node tree
Root and leaf are the same node; height and depth are zero
DSA Python
if not root.children:
        return 0
Tree with no children nodes (empty list)
No root found; functions handle empty input gracefully
DSA Python
return roots.pop() if roots else None
When to Use This Pattern
When you see a problem involving hierarchical data or parent-child relationships, recognize tree terminology to describe and navigate the structure effectively.
Common Mistakes
Mistake: Confusing depth and height as the same
Fix: Remember depth is distance from root down to node; height is distance from node down to furthest leaf
Mistake: Assuming leaves have children
Fix: Leaves are nodes with no children; check children list length
Summary
Defines key parts of a tree: root (start), leaves (ends), height (longest path down), depth (distance from root), and level (nodes at same depth).
Use when you need to understand or explain positions and distances of nodes in a tree structure.
The key insight is that depth and height measure distance in opposite directions from root and leaves, helping us navigate trees clearly.

Practice

(1/5)
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
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard