Count Total Nodes in Binary Tree in DSA Go

Mental Model

We want to find how many pieces (nodes) are in a tree by visiting each one exactly once.

Analogy: Imagine counting all the people in a family tree by visiting each person and adding one to your count.

    1
   / \
  2   3
 / 
4  

Dry Run Walkthrough

Input: Binary tree: 1 with left child 2 and right child 3; 2 has left child 4

Goal: Count all nodes in the tree

Step 1: Start at root node 1, count 1

Count so far: 1 (node 1)

Why: We begin counting from the root node

Step 2: Go to left child node 2, count 1 more

Count so far: 2 (nodes 1, 2)

Why: We count the left child node

Step 3: Go to left child of 2, node 4, count 1 more

Count so far: 3 (nodes 1, 2, 4)

Why: We count the left child of node 2

Step 4: Node 4 has no children, return count 1 for this subtree

Return 1 from node 4

Why: Leaf node counts as 1

Step 5: Node 2 has no right child, count 0 there

Return 0 from right child of node 2

Why: No node means count 0

Step 6: Total count at node 2 is 1 (itself) + 1 (left) + 0 (right) = 2

Return 2 from node 2

Why: Sum counts from children plus current node

Step 7: Go to right child node 3, count 1 more

Count so far: 1 (node 3)

Why: Count right child of root

Step 8: Node 3 has no children, return count 1

Return 1 from node 3

Why: Leaf node counts as 1

Step 9: Total count at root node 1 is 1 + 2 (left subtree) + 1 (right subtree) = 4

Return 4 from root node

Why: Sum counts from left and right subtrees plus root

Result:

1 -> 2 -> 4 -> null and 3 -> null
Total nodes counted: 4

Annotated Code

DSA Go

package main

import "fmt"

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

func countNodes(root *TreeNode) int {
    if root == nil {
        return 0
    }
    leftCount := countNodes(root.Left) // count nodes in left subtree
    rightCount := countNodes(root.Right) // count nodes in right subtree
    return 1 + leftCount + rightCount // add current node
}

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}

    total := countNodes(root)
    fmt.Printf("Total nodes counted: %d\n", total)
}

if root == nil { return 0 }

base case: no node means count zero

leftCount := countNodes(root.Left)

count nodes in left subtree

rightCount := countNodes(root.Right)

count nodes in right subtree

return 1 + leftCount + rightCount

sum counts from left, right, plus current node

Output

Total nodes counted: 4

Complexity Analysis

Time: O(n) because we visit each node exactly once

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

vs Alternative: Compared to iterative methods, recursion is simpler but uses call stack; iterative may use explicit stack with similar time

Edge Cases

Empty tree (root is nil)

Returns 0 nodes

DSA Go

if root == nil {
        return 0
    }

Single node tree

Returns 1 node count

DSA Go

return 1 + leftCount + rightCount

Tree with only left or only right children

Counts all nodes correctly by recursive calls

DSA Go

leftCount := countNodes(root.Left)
rightCount := countNodes(root.Right)

When to Use This Pattern

When you need to count or aggregate information from all nodes in a tree, use a recursive traversal pattern that sums results from subtrees.

Common Mistakes

Mistake: Forgetting to add 1 for the current node in the return statement
Fix: Always add 1 to the sum of left and right subtree counts to include the current node

Summary

Counts the total number of nodes in a binary tree by visiting each node once.

Use when you need to know how many nodes exist in a tree structure.

The key insight is to count nodes in left and right subtrees recursively and add one for the current node.