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).