Data Structures Theoryknowledge~6 mins

Height and depth of trees in Data Structures Theory - Full Explanation

Choose your learning style10 modes available

Learn Why Deep Visual Practice Challenge Project Recall Time

Start learning this pattern below

Jump into concepts and practice - no test required

Recommended

Test this pattern10 questions across easy, medium, and hard to know if this pattern is strong

Introduction

Imagine you have a family tree or an organizational chart. You want to know how far someone is from the top or how tall the whole tree is. Height and depth help us measure these distances in tree structures.

Explanation

Depth of a node

Depth tells us how far a node is from the root of the tree. We count the number of steps or edges from the root down to that node. The root itself has a depth of zero because it is the starting point.

Depth measures the distance from the root to a specific node.

Height of a node

Height tells us how far a node is from the farthest leaf below it. We count the number of steps from that node down to the deepest leaf in its subtree. A leaf node has a height of zero because it has no children.

Height measures the longest path from a node down to a leaf.

Height of the tree

The height of the whole tree is the height of the root node. It shows the longest path from the root down to any leaf in the tree. This tells us how tall or deep the entire tree is.

The tree's height is the height of its root node.

Relationship between height and depth

Depth and height measure distances in opposite directions: depth goes down from the root to a node, height goes down from a node to its leaves. Together, they help us understand the tree's shape and structure.

Depth and height are complementary ways to measure positions in a tree.

Real World Analogy

Think of a family tree where the oldest ancestor is at the top. The depth of a person is how many generations they are away from that ancestor. The height of a person is how many generations are below them until the youngest descendant.

Depth of a node → Number of generations from the oldest ancestor to a family member

Height of a node → Number of generations from a family member down to their youngest descendant

Height of the tree → Total number of generations from the oldest ancestor to the youngest descendant

Relationship between height and depth → Counting generations up from the ancestor versus down to descendants

Diagram

        ┌───── Root (depth=0, height=3) ─────┐
        │                                  │
    ┌───┴───┐                          ┌───┴───┐
    │       │                          │       │
 Node1   Node2(depth=1, height=1)  Node3   Node4
(depth=1, height=2)                (depth=1, height=0)
    │                               
  Leaf1 (depth=2, height=0)

This diagram shows a tree with nodes labeled by their depth and height values.

Key Facts

Depth → The number of edges from the root node to a given node.

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

Root node → The topmost node in a tree with depth zero.

Leaf node → A node with no children and height zero.

Tree height → The height of the root node, representing the longest path to any leaf.

Code Example

Data Structures Theory

class Node:
    def __init__(self, value):
        self.value = value
        self.children = []

def compute_depth(node, root, depth=0):
    if node == root:
        return depth
    for child in root.children:
        d = compute_depth(node, child, depth + 1)
        if d != -1:
            return d
    return -1

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

# Build a sample tree
root = Node('root')
child1 = Node('child1')
child2 = Node('child2')
leaf = Node('leaf')
root.children = [child1, child2]
child1.children = [leaf]

# Compute depth and height
print('Depth of leaf:', compute_depth(leaf, root))
print('Height of root:', compute_height(root))

OutputSuccess

Common Confusions

Thinking depth and height are the same measurement.

Thinking depth and height are the same measurement. Depth measures distance from the root down to a node, while height measures distance from a node down to its farthest leaf; they are opposite directions.

Assuming leaf nodes have height greater than zero.

Assuming leaf nodes have height greater than zero. Leaf nodes have height zero because they have no children below them.

Summary

Depth measures how far a node is from the root, counting edges downward.

Height measures how far a node is from its farthest leaf, counting edges downward.

The height of the tree is the height of its root node, showing the tree's overall size.

Practice

(1/5)

1. What does the depth of a node in a tree represent?

easy

A. The number of edges from the root to that node

B. The number of edges from that node to the farthest leaf

C. The total number of nodes in the tree

D. The number of children the node has

Height and depth of trees in Data Structures Theory - Full Explanation

Start learning this pattern below

Practice

Solution

Step 1: Understand the definition of depth

Step 2: Compare with other options

Final Answer:

Quick Check:

Solution

Step 1: Recall height definition for any node

Step 2: Apply to leaf node

Final Answer:

Quick Check:

Solution

Step 1: Identify the subtree rooted at node C

Step 2: Find longest path from C down to a leaf

Final Answer:

Quick Check:

Solution

Step 1: Recall definition of depth for root

Step 2: Identify error in student's statement

Final Answer:

Quick Check:

Solution

Step 1: Understand height of leaf nodes

Step 2: Apply to leaf at depth 4

Final Answer:

Quick Check: