Height of Binary Tree in DSA Go

Mental Model

The height of a binary tree is the longest path from the root to any leaf. We find it by checking how deep the tree goes.

Analogy: Imagine a family tree where height is how many generations you count from the oldest ancestor down to the youngest descendant.

    1
   / \
  2   3
 / 
4  

(Height is the longest path from 1 down to 4)

Dry Run Walkthrough

Input: Binary tree: root=1, left=2, right=3, left of 2=4

Goal: Find the height of this tree, which is the longest path from root to leaf

Step 1: Start at root node 1, check left subtree height

1 -> left subtree root=2, right subtree root=3

Why: We need to find height of left and right subtrees to compare

Step 2: At node 2, check left subtree height

2 -> left subtree root=4, right subtree null

Why: Continue down left side to find deepest leaf

Step 3: At node 4, both left and right are null, height is 1

4 -> left=null, right=null

Why: Leaf node height is 1

Step 4: Back to node 2, right subtree is null so height is 0, left subtree height is 1, so node 2 height is 1 + max(1,0) = 2

2 -> height=2

Why: Height at node is 1 plus max height of children

Step 5: At node 3, both children null, height is 1

3 -> height=1

Why: Leaf node height is 1

Step 6: Back to root 1, left subtree height=2, right subtree height=1, so height is 1 + max(2,1) = 3

1 -> height=3

Why: Root height is 1 plus max height of left and right

Result:

Height of tree = 3

Annotated Code

DSA Go

package main

import "fmt"

// TreeNode represents a node in binary tree
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// height returns the height of the binary tree rooted at node
func height(node *TreeNode) int {
    if node == nil {
        return 0 // base case: empty tree has height 0
    }
    leftHeight := height(node.Left)   // find height of left subtree
    rightHeight := height(node.Right) // find height of right subtree
    if leftHeight > rightHeight {
        return leftHeight + 1 // height is max of left/right plus 1 for current node
    }
    return rightHeight + 1
}

func main() {
    // build tree: 1
    //           /   \
    //          2     3
    //         /     
    //        4      
    root := &TreeNode{Val: 1}
    root.Left = &TreeNode{Val: 2}
    root.Right = &TreeNode{Val: 3}
    root.Left.Left = &TreeNode{Val: 4}

    h := height(root)
    fmt.Printf("Height of tree = %d\n", h)
}

if node == nil { return 0 }

base case: empty subtree has height 0

leftHeight := height(node.Left)

recursively find height of left subtree

rightHeight := height(node.Right)

recursively find height of right subtree

if leftHeight > rightHeight { return leftHeight + 1 }

height is max of left/right subtree heights plus 1 for current node

return rightHeight + 1

return height if right subtree is taller or equal

Output

Height of tree = 3

Complexity Analysis

Time: O(n) because we visit every node once to compute height

Space: O(h) where h is tree height due to recursion call stack

vs Alternative: Compared to iterative BFS which uses queue and O(n) space, recursion is simpler but uses call stack proportional to height

Edge Cases

Empty tree (root is nil)

Returns height 0 without error

DSA Go

if node == nil { return 0 }

Single node tree

Returns height 1 as only root exists

DSA Go

if node == nil { return 0 }

Left skewed tree (all nodes only have left child)

Height equals number of nodes in path down left

DSA Go

leftHeight := height(node.Left)

When to Use This Pattern

When asked for the longest path from root to leaf or depth of a tree, use the height pattern by recursively checking left and right subtree heights.

Common Mistakes

Mistake: Returning sum of left and right subtree heights instead of max
Fix: Return max of left and right subtree heights plus 1

Mistake: Not handling nil node base case causing runtime error
Fix: Add base case to return 0 when node is nil

Summary

Calculates the longest path from root to any leaf in a binary tree.

Use when you need to know how deep or tall a tree is.

The height is 1 plus the maximum height of its left and right subtrees.