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.

Practice

1. What does the height of a binary tree represent?

easy

A. The number of children of the root node

B. The total number of nodes in the tree

C. The number of leaf nodes in the tree

D. The number of edges on the longest path from root to a leaf

Solution

1. Step 1: Understand the definition of height in a binary tree

   The height is the longest path from the root node down to the farthest leaf node, counted by edges.

2. Step 2: Compare options with the definition

   Only The number of edges on the longest path from root to a leaf correctly describes the height as the number of edges on the longest root-to-leaf path.

3. Final Answer:

   The number of edges on the longest path from root to a leaf -> Option D

4. Quick Check:

   Height = longest root-to-leaf edges [OK]

Hint: Height counts edges, not nodes, from root to deepest leaf [OK]

Common Mistakes:

• Confusing height with total nodes
• Counting nodes instead of edges
• Thinking height is number of leaves

2. Which Go function signature correctly defines a recursive function to find the height of a binary tree node?

easy

A. func height(root Node) string

B. func height(root *Node) int

C. func height(root *Node) bool

D. func height(root Node) float64

Solution

1. Step 1: Identify correct parameter and return types for height function

   The function should accept a pointer to a Node and return an integer representing height.

2. Step 2: Match options with correct signature

   func height(root *Node) int matches: func height(root *Node) int. Others have wrong parameter types or return types.

3. Final Answer:

   func height(root *Node) int -> Option B

4. Quick Check:

   Pointer input and int output for height [OK]

Hint: Height returns int; input is pointer to Node [OK]

Common Mistakes:

• Using value instead of pointer for root
• Returning wrong data type like bool or string
• Incorrect function parameter types

3. What is the output of this Go code snippet that calculates the height of a binary tree?

package main

import "fmt"

type Node struct {
    left, right *Node
}

func height(root *Node) int {
    if root == nil {
        return 0
    }
    leftHeight := height(root.left)
    rightHeight := height(root.right)
    if leftHeight > rightHeight {
        return leftHeight + 1
    }
    return rightHeight + 1
}

func main() {
    root := &Node{
        left: &Node{},
        right: &Node{
            right: &Node{},
        },
    }
    fmt.Println(height(root))
}

medium

A. 3

B. 2

C. 4

D. 1

Solution

1. Step 1: Analyze the tree structure

   The root has left child (leaf) and right child with its own right child (leaf). The longest path is root -> right -> right, which has 3 nodes and 2 edges.

2. Step 2: Calculate height as edges + 1

   The function returns 1 + max height of children. The longest path has 2 edges, so height = 3.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Height counts edges + 1 for nodes [OK]

Hint: Count longest path edges + 1 for height [OK]

Common Mistakes:

• Counting nodes instead of edges
• Ignoring nil child nodes
• Confusing left and right subtree heights

4. Identify the bug in this Go function that calculates the height of a binary tree:

func height(root *Node) int {
    if root == nil {
        return -1
    }
    leftHeight := height(root.left)
    rightHeight := height(root.right)
    if leftHeight > rightHeight {
        return leftHeight + 1
    }
    return rightHeight + 1
}

medium

A. Returning -1 for nil node causes incorrect height calculation

B. Missing base case for leaf nodes

C. Using pointers incorrectly for root

D. Not handling empty tree separately

Solution

1. Step 1: Check base case return value

   The function returns -1 for nil nodes, which causes height to be off by one compared to standard definition.

2. Step 2: Understand correct base case for height

   Height of empty tree should be 0 or 0 edges; returning -1 leads to negative heights and incorrect results.

3. Final Answer:

   Returning -1 for nil node causes incorrect height calculation -> Option A

4. Quick Check:

   Base case should return 0 for nil [OK]

Hint: Base case for nil must return 0, not -1 [OK]

Common Mistakes:

• Returning -1 instead of 0 for nil
• Confusing base case with leaf node
• Not adding 1 after recursive calls

5. Given a binary tree where each node stores an integer, write a recursive Go function to find the height of the tree and also return the sum of all node values at the deepest level. Which approach correctly combines these tasks?

hard

A. Use iterative BFS to find height and sum nodes at last level in one pass

B. Calculate height first, then traverse tree again to sum deepest level nodes separately

C. Use a recursive function that returns both height and sum at deepest level by comparing left and right subtree results

D. Use recursion to sum all nodes and ignore height calculation

Solution

1. Step 1: Understand combined task requirements

   We need height and sum of nodes at deepest level in one function efficiently.

2. Step 2: Evaluate approaches

   Use a recursive function that returns both height and sum at deepest level by comparing left and right subtree results uses recursion returning height and sum together, avoiding multiple traversals.

3. Step 3: Compare other options

   Calculate height first, then traverse tree again to sum deepest level nodes separately does two traversals, less efficient. Use iterative BFS to find height and sum nodes at last level in one pass is valid but iterative BFS is not recursive. Use recursion to sum all nodes and ignore height calculation ignores height, so incomplete.

4. Final Answer:

   Use a recursive function that returns both height and sum at deepest level by comparing left and right subtree results -> Option C

5. Quick Check:

   Combine height and sum in one recursive pass [OK]

Hint: Return height and sum together recursively to avoid extra traversal [OK]

Common Mistakes:

• Doing two separate traversals
• Ignoring sum at deepest level
• Using iterative approach when recursion asked