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

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

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))

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.