Count Total Nodes in Binary Tree in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Counting Nodes in a Simple Binary Tree

What is the output of the following Go code that counts total nodes in a binary tree?

DSA Go

package main
import "fmt"
type Node struct {
    Val   int
    Left  *Node
    Right *Node
}
func countNodes(root *Node) int {
    if root == nil {
        return 0
    }
    return 1 + countNodes(root.Left) + countNodes(root.Right)
}
func main() {
    root := &Node{Val: 1}
    root.Left = &Node{Val: 2}
    root.Right = &Node{Val: 3}
    root.Left.Left = &Node{Val: 4}
    fmt.Println(countNodes(root))
}

A 3

B 4

C 5

D 6

💡 Hint

Count each node including root, left subtree, and right subtree.

The tree has nodes with values 1, 2, 3, and 4. Total nodes = 4.

❓ Predict Output

intermediate

Count Nodes in a Skewed Binary Tree

What is the output of this Go code counting nodes in a skewed binary tree?

DSA Go

package main
import "fmt"
type Node struct {
    Val   int
    Left  *Node
    Right *Node
}
func countNodes(root *Node) int {
    if root == nil {
        return 0
    }
    return 1 + countNodes(root.Left) + countNodes(root.Right)
}
func main() {
    root := &Node{Val: 10}
    root.Right = &Node{Val: 20}
    root.Right.Right = &Node{Val: 30}
    root.Right.Right.Right = &Node{Val: 40}
    fmt.Println(countNodes(root))
}

A 3

B 5

C 6

D 4

💡 Hint

Count all nodes along the right side.

The tree has nodes 10, 20, 30, and 40 linked rightwards. Total nodes = 4.

🔧 Debug

advanced

Identify the Error in Node Counting Function

What error will this Go code produce when counting nodes in a binary tree?

DSA Go

package main
import "fmt"
type Node struct {
    Val   int
    Left  *Node
    Right *Node
}
func countNodes(root *Node) int {
    if root == nil {
        return 1
    }
    return 1 + countNodes(root.Left) + countNodes(root.Right)
}
func main() {
    root := &Node{Val: 1}
    fmt.Println(countNodes(root))
}

A Returns 1 for empty tree, causing incorrect count

B Correctly returns 0 for empty tree

C Runtime panic due to nil pointer dereference

D Compilation error due to missing return statement

💡 Hint

Check the base case return value for nil node.

Returning 1 for nil node counts empty children as nodes, inflating count.

🧠 Conceptual

advanced

Time Complexity of Counting Nodes in Binary Tree

What is the time complexity of counting total nodes in a binary tree using recursion?

A O(n), where n is the number of nodes

B O(log n), where n is the number of nodes

C O(n^2), where n is the number of nodes

D O(1), constant time

💡 Hint

Each node is visited once in the recursion.

The function visits every node once, so time is proportional to number of nodes.

🚀 Application

expert

Count Nodes in a Binary Tree with Missing Children

Given the binary tree below, what is the total number of nodes? Structure: - Root node 5 - Left child 3 - Right child 8 - Left child of 3 is 1 - Right child of 3 is nil - Left child of 8 is nil - Right child of 8 is 10 Use the countNodes function below: func countNodes(root *Node) int { if root == nil { return 0 } return 1 + countNodes(root.Left) + countNodes(root.Right) }

A 4

B 6

C 5

D 3

💡 Hint

Count all nodes including those with nil children.

Nodes are 5, 3, 8, 1, and 10. Total is 5 nodes.