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.

Practice

1. What does the function to count total nodes in a binary tree do?

easy

A. It counts only the leaf nodes of the tree.

B. It counts all nodes including root, left, and right children.

C. It counts only the nodes on the left side of the tree.

D. It counts only the nodes on the right side of the tree.

Solution

1. Step 1: Understand node counting in binary tree

   Counting total nodes means including every node: root, left child, and right child recursively.

2. Step 2: Compare options with definition

   Only the option that says 'It counts all nodes including root, left, and right children.' includes all nodes, others limit to parts of the tree.

3. Final Answer:

   It counts all nodes including root, left, and right children. -> Option B

4. Quick Check:

   Total nodes = all nodes in tree [OK]

Hint: Count every node, not just leaves or sides [OK]

Common Mistakes:

• Counting only leaf nodes
• Ignoring root node
• Counting only one subtree

2. Which of the following Go function signatures correctly defines a function to count nodes in a binary tree with root type *Node?

easy

A. func countNodes(root *Node) string

B. func countNodes(root Node) int

C. func countNodes(root *Node) int

D. func countNodes(root Node) bool

Solution

1. Step 1: Identify correct parameter type

   Binary tree root is usually a pointer to Node, so *Node is correct.

2. Step 2: Identify correct return type

   Counting nodes returns an integer, so return type int is correct.

3. Final Answer:

   func countNodes(root *Node) int -> Option C

4. Quick Check:

   Pointer parameter and int return type [OK]

Hint: Use pointer receiver and int return for count function [OK]

Common Mistakes:

• Passing Node by value instead of pointer
• Returning wrong type like string or bool
• Missing pointer in parameter

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

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

medium

A. 6

B. 3

C. 5

D. 4

Solution

1. Step 1: Count nodes in the tree structure

   Nodes are: 1 (root), 2 (left), 3 (right), 4 (left-left). Total = 4 nodes.

2. Step 2: Verify counting logic in code

   Code counts root + left subtree + right subtree recursively, so total nodes = 4.

3. Final Answer:

   4 -> Option D

4. Quick Check:

   Count nodes recursively = 4 [OK]

Hint: Add 1 for root plus counts of left and right subtrees [OK]

Common Mistakes:

• Counting only root and immediate children
• Forgetting to count left-left node
• Misreading tree structure

4. Identify the error in this Go function to count total nodes in a binary tree:

func countNodes(root *Node) int {
  if root == nil {
    return 1
  }
  return 1 + countNodes(root.Left) + countNodes(root.Right)
}

medium

A. Returns 1 when root is nil, should return 0.

B. Missing base case for leaf nodes.

C. Returns sum without counting current node.

D. Function signature is incorrect.

Solution

1. Step 1: Check base case for nil node

   When root is nil, it means no node, so should return 0, not 1.

2. Step 2: Verify the counting logic

   The return statement correctly adds 1 for the current node plus recurses on left and right subtrees.

3. Final Answer:

   Returns 1 when root is nil, should return 0. -> Option A

4. Quick Check:

   Nil node count = 0, not 1 [OK]

Hint: Base case for nil node must return 0 [OK]

Common Mistakes:

• Returning 1 for nil node
• Not adding 1 for current node
• Incorrect base case logic

5. Given a binary tree where each node has a value, how would you modify the countNodes function to count only nodes with even values?

hard

A. Add a check: if node value is even, add 1; else add 0, then recurse.

B. Count all nodes and subtract nodes with odd values after traversal.

C. Only traverse left subtree if node value is even.

D. Return 1 for every node regardless of value.

Solution

1. Step 1: Add condition to count only even nodes

   Check if current node's value is even; if yes, count 1, else 0.

2. Step 2: Recursively count even nodes in left and right subtrees

   Sum counts from left and right subtrees with current node's count.

3. Final Answer:

   Add a check: if node value is even, add 1; else add 0, then recurse. -> Option A

4. Quick Check:

   Count only even nodes by conditional addition [OK]

Hint: Add 1 only if node value is even, else 0 [OK]

Common Mistakes:

• Counting all nodes then subtracting odd nodes
• Skipping subtrees based on node value
• Ignoring node values in count