Diameter of Binary Tree in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Diameter Calculation for a Simple Tree

What is the output of the following Go code that calculates the diameter of a binary tree?

DSA Go

package main
import "fmt"
type TreeNode struct {
    Val int
    Left *TreeNode
    Right *TreeNode
}

func diameterOfBinaryTree(root *TreeNode) int {
    maxDiameter := 0
    var depth func(node *TreeNode) int
    depth = func(node *TreeNode) int {
        if node == nil {
            return 0
        }
        left := depth(node.Left)
        right := depth(node.Right)
        if left+right > maxDiameter {
            maxDiameter = left + right
        }
        if left > right {
            return left + 1
        }
        return right + 1
    }
    depth(root)
    return maxDiameter
}

func main() {
    root := &TreeNode{Val: 1}
    root.Left = &TreeNode{Val: 2}
    root.Right = &TreeNode{Val: 3}
    root.Left.Left = &TreeNode{Val: 4}
    root.Left.Right = &TreeNode{Val: 5}
    fmt.Println(diameterOfBinaryTree(root))
}

A 2

B 4

C 3

D 5

💡 Hint

Think about the longest path between any two nodes in the tree.

The diameter is the longest path between two nodes. Here, the longest path goes through nodes 4 -> 2 -> 1 -> 3 or 5 -> 2 -> 1 -> 3, which has length 3 edges.

🧠 Conceptual

intermediate

Understanding Diameter Definition

Which of the following best describes the diameter of a binary tree?

A The number of edges on the longest path between any two nodes in the tree.

B The height of the tree from the root node to the deepest leaf.

C The total number of nodes in the tree.

D The number of nodes on the longest path between any two nodes in the tree.

💡 Hint

Diameter counts edges, not nodes.

Diameter is defined as the number of edges on the longest path between any two nodes, not the number of nodes or height.

🔧 Debug

advanced

Identify the Error in Diameter Calculation

What error will occur when running this Go code to calculate the diameter of a binary tree?

DSA Go

package main
import "fmt"
type TreeNode struct {
    Val int
    Left *TreeNode
    Right *TreeNode
}

func diameterOfBinaryTree(root *TreeNode) int {
    maxDiameter := 0
    var depth func(node *TreeNode) int
    depth = func(node *TreeNode) int {
        if node == nil {
            return 0
        }
        left := depth(node.Left)
        right := depth(node.Right)
        if left+right > maxDiameter {
            maxDiameter = left + right
        }
        return max(left, right) + 1
    }
    depth(root)
    return maxDiameter
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func main() {
    root := &TreeNode{Val: 1}
    root.Left = &TreeNode{Val: 2}
    root.Right = &TreeNode{Val: 3}
    fmt.Println(diameterOfBinaryTree(root))
}

A Output is 2

B Runtime panic: nil pointer dereference

C Compilation error: undefined function max

D Output is 3

💡 Hint

Check if the max function is defined and used correctly.

The max function is defined and used correctly. The diameter for this tree is 2 edges (path 2 -> 1 -> 3).

🚀 Application

advanced

Diameter of Unbalanced Binary Tree

Given the following unbalanced binary tree, what is the diameter?

DSA Go

package main
import "fmt"
type TreeNode struct {
    Val int
    Left *TreeNode
    Right *TreeNode
}

func diameterOfBinaryTree(root *TreeNode) int {
    maxDiameter := 0
    var depth func(node *TreeNode) int
    depth = func(node *TreeNode) int {
        if node == nil {
            return 0
        }
        left := depth(node.Left)
        right := depth(node.Right)
        if left+right > maxDiameter {
            maxDiameter = left + right
        }
        if left > right {
            return left + 1
        }
        return right + 1
    }
    depth(root)
    return maxDiameter
}

func main() {
    root := &TreeNode{Val: 1}
    root.Left = &TreeNode{Val: 2}
    root.Left.Left = &TreeNode{Val: 3}
    root.Left.Left.Left = &TreeNode{Val: 4}
    root.Right = &TreeNode{Val: 5}
    fmt.Println(diameterOfBinaryTree(root))
}

A 3

B 4

C 2

D 5

💡 Hint

Consider the longest path between two nodes, which may not pass through the root.

The longest path is from node 4 to node 5 (4 -> 3 -> 2 -> 1 -> 5), which has 4 edges. The code correctly computes it as 4 (left depth from root = 3, right = 1, 3 + 1 = 4).

🧠 Conceptual

expert

Effect of Diameter Calculation on Tree Traversal Complexity

What is the time complexity of calculating the diameter of a binary tree using the depth-first search approach shown in the code examples?

A O(1), since diameter is calculated using constant time operations

B O(n^2), because depth is calculated multiple times for each node

C O(log n), assuming the tree is balanced

D O(n), where n is the number of nodes in the tree

💡 Hint

Each node is visited once in the depth-first search.

The algorithm visits each node once, calculating depth and updating diameter, so the time complexity is linear O(n).

Practice

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

easy

A. The length of the longest path between any two nodes in the tree

B. The number of nodes in the tree

C. The height of the tree

D. The number of leaf nodes in the tree

Solution

1. Step 1: Understand the diameter definition

   The diameter is the longest path between any two nodes, which may or may not pass through the root.

2. Step 2: Differentiate from other tree properties

   Height is the longest path from root to leaf, number of nodes counts all nodes, leaves count only leaf nodes.

3. Final Answer:

   The length of the longest path between any two nodes in the tree -> Option A

4. Quick Check:

   Diameter = longest path between nodes [OK]

Hint: Diameter is longest path, not height or node count [OK]

Common Mistakes:

• Confusing diameter with height
• Thinking diameter counts nodes instead of edges
• Assuming diameter must pass through root

2. Which Go function signature correctly represents a helper function to compute the height of a binary tree node for diameter calculation?

easy

A. func height(node int) int

B. func height(node *TreeNode) int

C. func height(node *TreeNode) bool

D. func height(node TreeNode) string

Solution

1. Step 1: Identify correct parameter type

   The function should accept a pointer to TreeNode to handle nil nodes and avoid copying.

2. Step 2: Identify correct return type

   Height is an integer value representing depth, so return type must be int.

3. Final Answer:

   func height(node *TreeNode) int -> Option B

4. Quick Check:

   Pointer input and int output for height [OK]

Hint: Height function uses pointer receiver and returns int [OK]

Common Mistakes:

• Using value receiver instead of pointer
• Returning wrong type like string or bool
• Passing int instead of TreeNode pointer

3. Given the following Go code snippet, what is the diameter of the binary tree?

type TreeNode struct {
    Val int
    Left *TreeNode
    Right *TreeNode
}

root := &TreeNode{Val: 1}
root.Left = &TreeNode{Val: 2}
root.Right = &TreeNode{Val: 3}
root.Left.Left = &TreeNode{Val: 4}
root.Left.Right = &TreeNode{Val: 5}

// Diameter function uses height helper internally
func diameterOfBinaryTree(root *TreeNode) int {
    maxDiameter := 0
    var height func(node *TreeNode) int
    height = func(node *TreeNode) int {
        if node == nil {
            return 0
        }
        leftHeight := height(node.Left)
        rightHeight := height(node.Right)
        if leftHeight+rightHeight > maxDiameter {
            maxDiameter = leftHeight + rightHeight
        }
        if leftHeight > rightHeight {
            return leftHeight + 1
        }
        return rightHeight + 1
    }
    height(root)
    return maxDiameter
}

fmt.Println(diameterOfBinaryTree(root))

medium

A. 4

B. 2

C. 3

D. 5

Solution

1. Step 1: Calculate heights of subtrees

   Left subtree of root has height 2 (nodes 2->4 or 2->5), right subtree height is 1 (node 3).

2. Step 2: Calculate diameter as sum of left and right heights

   Diameter = leftHeight + rightHeight = 2 + 1 = 3 edges, but diameter counts edges, so longest path is 3 edges which means 4 nodes.

3. Final Answer:

   3 -> Option C

4. Quick Check:

   Longest path length = 3 edges [OK]

Hint: Diameter = sum of left and right subtree heights at max node [OK]

Common Mistakes:

• Counting nodes instead of edges for diameter
• Ignoring one subtree height
• Confusing height with diameter

4. Identify the bug in this Go code snippet for computing the diameter of a binary tree:

func diameterOfBinaryTree(root *TreeNode) int {
    maxDiameter := 0
    var height func(node *TreeNode) int
    height = func(node *TreeNode) int {
        if node == nil {
            return 0
        }
        leftHeight := height(node.Left)
        rightHeight := height(node.Right)
        maxDiameter = leftHeight + rightHeight
        if leftHeight > rightHeight {
            return leftHeight + 1
        }
        return rightHeight + 1
    }
    height(root)
    return maxDiameter
}

medium

A. Function does not call height recursively

B. height function returns wrong type

C. Missing base case for nil node

D. maxDiameter is overwritten without checking max value

Solution

1. Step 1: Analyze maxDiameter update

   maxDiameter is assigned leftHeight + rightHeight every time, overwriting previous max without comparison.

2. Step 2: Correct maxDiameter update

   Should update maxDiameter only if leftHeight + rightHeight is greater than current maxDiameter.

3. Final Answer:

   maxDiameter is overwritten without checking max value -> Option D

4. Quick Check:

   Use max check before assignment [OK]

Hint: Update maxDiameter only if new value is greater [OK]

Common Mistakes:

• Overwriting maxDiameter without max check
• Forgetting base case for nil node
• Not calling height recursively

5. You want to find the diameter of a binary tree but also return the path nodes forming that diameter. Which approach correctly extends the diameter calculation in Go?

hard

A. Modify height function to return both height and path, update max path when diameter increases

B. Calculate diameter first, then do a separate BFS to find path

C. Store all paths in a global slice and pick the longest after traversal

D. Use only height function and return diameter length without path

Solution

1. Step 1: Extend height function to track paths

   Modify the recursive height function to return both height and the path nodes from current node to leaf.

2. Step 2: Update max diameter and store path

   When leftHeight + rightHeight exceeds maxDiameter, update maxDiameter and store concatenated path from left and right subtrees through current node.

3. Step 3: Return stored path after traversal

   After full traversal, return the stored path representing the diameter.

4. Final Answer:

   Modify height function to return both height and path, update max path when diameter increases -> Option A

5. Quick Check:

   Track height and path together for diameter path [OK]

Hint: Return height and path from helper to track diameter path [OK]

Common Mistakes:

• Trying to find path after diameter without tracking
• Storing all paths wastes memory
• Ignoring path tracking in recursion