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.

Practice

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

easy

A. The topmost node with no parent

B. A node with no children

C. Any node at the lowest level

D. A node with exactly two children

Solution

1. Step 1: Understand the root node definition

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

2. Step 2: Differentiate root from other nodes

   Leaf nodes have no children, but root specifically has no parent. Lowest level nodes are leaves or internal nodes, not necessarily root.

3. Final Answer:

   The topmost node with no parent -> Option A

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 must have children
• Assuming root is at the lowest level

2. Which of the following is the correct way to declare a tree node struct in Go with integer data and pointers to left and right children?

easy

A. type Node struct { data int, left &Node, right &Node }

B. type Node struct { data int, left *Node, right *Node }

C. type Node struct { data int, left Node, right Node }

D. type Node struct { data int, left Node*, right Node* }

Solution

1. Step 1: Recall Go pointer syntax

   In Go, pointers are declared with * before the type, e.g., *Node.

2. Step 2: Check each option's pointer usage

   type Node struct { data int, left *Node, right *Node } uses *Node correctly. type Node struct { data int, left Node, right Node } uses Node (value, not pointer). type Node struct { data int, left &Node, right &Node } uses &Node which is invalid syntax. type Node struct { data int, left Node*, right Node* } uses Node* which is invalid in Go.

3. Final Answer:

   type Node struct { data int, left *Node, right *Node } -> Option B

4. Quick Check:

   Pointer syntax in Go = *Type [OK]

Hint: Use *Type for pointers in Go structs [OK]

Common Mistakes:

• Using value type instead of pointer for children
• Using &Type or Type* which are invalid in Go
• Using semicolons instead of commas in struct fields

3. Given the following tree structure in Go, what is the depth of node with value 5?

type Node struct {
  data  int
  left  *Node
  right *Node
}

root := &Node{data: 1}
root.left = &Node{data: 2}
root.right = &Node{data: 3}
root.left.left = &Node{data: 4}
root.left.right = &Node{data: 5}

medium

A. 2

B. 1

C. 3

D. 4

Solution

1. Step 1: Understand depth definition

   Depth of a node is the number of edges from the root to that node.

2. Step 2: Trace path from root to node 5

   Path: 1 (root) -> 2 -> 5. Number of edges = 2.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Depth = edges from root = 2 [OK]

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

Common Mistakes:

• Counting nodes instead of edges
• Confusing depth with height
• Miscounting path length

4. Consider this Go code snippet for a binary tree node:

type Node struct {
  data  int
  left  *Node
  right *Node
}

func isLeaf(n *Node) bool {
  return n.left == nil && n.right == nil
}

root := &Node{data: 10}
root.left = &Node{data: 20}
root.right = &Node{data: 30}
root.left.left = &Node{data: 40}

fmt.Println(isLeaf(root.left))

What is the output and why?

medium

A. true

B. Runtime panic

C. Compilation error

D. false

Solution

1. Step 1: Understand isLeaf function

   It returns true if both left and right children are nil (no children).

2. Step 2: Check root.left node children

   root.left has left child (40) but no right child, so left != nil, right == nil.

3. Step 3: Evaluate isLeaf(root.left)

   Since left is not nil, isLeaf returns false.

4. Final Answer:

   false -> Option D

5. Quick Check:

   Leaf = no children, root.left has left child [OK]

Hint: Leaf nodes have no children; check both left and right nil [OK]

Common Mistakes:

• Assuming node with one child is leaf
• Confusing nil checks causing panic
• Expecting true without checking both children

5. You have a binary tree where the root is at level 0. If a node is at level 3, what is its height assuming the tree height is 5? Also, which node is at level 0? Choose the correct pair of answers.

hard

A. Height = 5; Root node is at level 0

B. Height = 3; Leaf node is at level 0

C. Height = 2; Root node is at level 0

D. Height = 2; Leaf node is at level 0

Solution

1. Step 1: Calculate height of node at level 3

   Height = total tree height - node level = 5 - 3 = 2.

2. Step 2: Identify node at level 0

   By definition, root node is at level 0.

3. Final Answer:

   Height = 2; Root node is at level 0 -> Option C

4. Quick Check:

   Height = 5 - 3 = 2; Root at level 0 [OK]

Hint: Height = tree height - level; root always level 0 [OK]

Common Mistakes:

• Confusing height with level
• Assuming leaf node at level 0
• Calculating height as level number