Tree Terminology Root Leaf Height Depth Level in DSA Go

Mental Model

A tree is a structure with a starting point called root, ends called leaves, and measures like height and depth that tell how far nodes are from the root.

Analogy: Imagine a family tree: the oldest ancestor is the root, youngest children with no kids are leaves, height is the longest family line, depth is how many generations from the ancestor, and level is the generation number.

        Root (Level 0)
          ↓
       Node A (Level 1)
       /       \
Leaf B (2)   Leaf C (2)

Legend:
- Root: starting node
- Leaf: end node with no children
- Level: generation number starting at 0
- Depth: distance from root
- Height: longest path from node to leaf

Dry Run Walkthrough

Input: Tree with root node 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

Root is node 1

Why: Root is the starting point with no parent

Step 2: Find leaves (nodes with no children)

Leaves: 3, 4
Tree:
1 -> 2 -> 4
     ↓
     3

Why: Leaves have no children, ends of branches

Step 3: Calculate depth (distance from root) for each node

Depths:
1: 0 (root)
2: 1
3: 1
4: 2

Why: Depth counts steps from root to node

Step 4: Calculate height (longest path from node to leaf)

Heights:
4: 0 (leaf)
3: 0 (leaf)
2: 1 (to leaf 4)
1: 2 (to leaf 4)

Why: Height measures longest path down to leaf

Step 5: Assign level same as depth for each node

Levels:
1: 0
2: 1
3: 1
4: 2

Why: Level is generation number, same as depth

Result:

Final tree:
1 (root, depth=0, height=2, level=0)
├─ 2 (depth=1, height=1, level=1)
│  └─ 4 (leaf, depth=2, height=0, level=2)
└─ 3 (leaf, depth=1, height=0, level=1)

Annotated Code

DSA Go

package main

import "fmt"

// Node represents a tree node
type Node struct {
    val      int
    children []*Node
}

// height returns the height of the node
func height(node *Node) int {
    if node == nil || len(node.children) == 0 {
        return 0 // leaf node height is 0
    }
    maxHeight := 0
    for _, child := range node.children {
        h := height(child) // recursive height of child
        if h > maxHeight {
            maxHeight = h
        }
    }
    return maxHeight + 1 // add 1 for current node
}

// depthMap stores depth of each node
func depthMap(node *Node, depth int, depths map[int]int) {
    if node == nil {
        return
    }
    depths[node.val] = depth // record depth
    for _, child := range node.children {
        depthMap(child, depth+1, depths) // recurse with depth+1
    }
}

// findLeaves collects leaf nodes
func findLeaves(node *Node, leaves *[]int) {
    if node == nil {
        return
    }
    if len(node.children) == 0 {
        *leaves = append(*leaves, node.val) // leaf found
        return
    }
    for _, child := range node.children {
        findLeaves(child, leaves)
    }
}

func main() {
    // Build tree:
    // 1
    // ├─ 2
    // │  └─ 4
    // └─ 3
    n4 := &Node{val: 4}
    n3 := &Node{val: 3}
    n2 := &Node{val: 2, children: []*Node{n4}}
    root := &Node{val: 1, children: []*Node{n2, n3}}

    // Root
    fmt.Println("Root:", root.val)

    // Leaves
    leaves := []int{}
    findLeaves(root, &leaves)
    fmt.Println("Leaves:", leaves)

    // Depths
    depths := map[int]int{}
    depthMap(root, 0, depths)
    fmt.Println("Depths:")
    for k, v := range depths {
        fmt.Printf("Node %d: %d\n", k, v)
    }

    // Heights
    fmt.Println("Heights:")
    nodes := []*Node{root, n2, n3, n4}
    for _, n := range nodes {
        h := height(n)
        fmt.Printf("Node %d: %d\n", n.val, h)
    }

    // Levels (same as depth)
    fmt.Println("Levels:")
    for k, v := range depths {
        fmt.Printf("Node %d: %d\n", k, v)
    }
}

if node == nil || len(node.children) == 0 { return 0 }

Return 0 height for leaf or empty node

for _, child := range node.children { h := height(child); if h > maxHeight { maxHeight = h } }

Find max height among children

depths[node.val] = depth

Record current node depth

for _, child := range node.children { depthMap(child, depth+1, depths) }

Recurse to children with increased depth

if len(node.children) == 0 { *leaves = append(*leaves, node.val); return }

Add node to leaves if no children

Output

Root: 1

Leaves: [4 3]

Depths:

Node 1: 0

Node 2: 1

Node 3: 1

Node 4: 2

Heights:

Node 1: 2

Node 2: 1

Node 3: 0

Node 4: 0

Levels:

Node 1: 0

Node 2: 1

Node 3: 1

Node 4: 2

Complexity Analysis

Time: O(n) because we visit each node once to calculate height, depth, and find leaves

Space: O(n) for recursion stack and maps storing depths and leaves

vs Alternative: Compared to iterative methods, recursion here is simpler and direct but uses call stack; iterative may need explicit stack

Edge Cases

Empty tree (root is nil)

Functions return zero or empty results without error

DSA Go

if node == nil { return } in depthMap and findLeaves

Single node tree (only root)

Root is also leaf; height and depth are zero

DSA Go

if len(node.children) == 0 { return 0 } in height

Tree with multiple leaves at different depths

Leaves correctly identified; heights and depths calculated per node

DSA Go

recursive calls in height and depthMap

When to Use This Pattern

When a problem asks about positions or distances of nodes in a tree, use root, leaf, height, depth, and level concepts to understand node relationships and measure paths.

Common Mistakes

Mistake: Confusing height and depth as the same
Fix: Remember depth is distance from root down to node; height is distance from node down to farthest leaf

Summary

Defines key terms to describe tree nodes and their positions: root, leaf, height, depth, and level.

Use when you need to understand or measure how nodes relate in a tree structure.

The key insight is that depth and level count steps down from root, while height counts steps down to leaves.