Count Total Nodes in Binary Tree in DSA Go - Build from Scratch

Count Total Nodes in Binary Tree

📖 Scenario: Imagine you are working with a family tree application. Each person is a node in a binary tree, where each node can have up to two children (left and right). You want to find out how many people (nodes) are in the family tree.

🎯 Goal: You will build a simple binary tree in Go and write a function to count the total number of nodes in the tree.

📋 What You'll Learn

Create a binary tree with exactly 5 nodes using a struct called Node

Add a variable called root that points to the root node of the tree

Write a recursive function called countNodes that returns the total number of nodes in the tree

Print the total number of nodes using fmt.Println

💡 Why This Matters

🌍 Real World

Counting nodes in a tree is useful in many applications like file systems, organizational charts, and family trees.

💼 Career

Understanding tree traversal and recursion is essential for software engineering roles involving data structures and algorithms.

1

Create the Binary Tree Structure and Nodes

Create a struct called Node with two fields: left and right of type *Node. Then create 5 nodes named node1 to node5. Connect them to form this tree:

node1 is root
node1.left = node2
node1.right = node3
node2.left = node4
node2.right = node5

Finally, create a variable called root that points to node1.

DSA Go

package main

import "fmt"

type Node struct {
    left  *Node
    right *Node
}

func main() {
    // Create nodes node1 to node5
    // Connect nodes as described
    // Create root pointing to node1
    // Your code here
}

Hint

Define the Node struct first. Then create each node using &Node{}. Connect the nodes by assigning the left and right fields. Finally, set root to point to node1.

2

Add a Helper Function to Count Nodes

Create a function called countNodes that takes a parameter node of type *Node and returns an int. This function will be used to count nodes recursively. For now, just add the function signature and return 0 inside the function.

DSA Go

package main

import "fmt"

type Node struct {
    left  *Node
    right *Node
}

func countNodes(node *Node) int {
    // Your code here
    return 0
}

func main() {
    node1 := &Node{}
    node2 := &Node{}
    node3 := &Node{}
    node4 := &Node{}
    node5 := &Node{}

    node1.left = node2
    node1.right = node3
    node2.left = node4
    node2.right = node5

    root := node1

    _ = root
}

Hint

Define the function countNodes with parameter node *Node and return type int. For now, just return 0 to complete the function.

3

Implement Recursive Logic to Count Nodes

Inside the countNodes function, write code to count nodes recursively. If node is nil, return 0. Otherwise, return 1 plus the count of nodes in the left subtree plus the count of nodes in the right subtree. Use countNodes(node.left) and countNodes(node.right) for recursion.

DSA Go

package main

import "fmt"

type Node struct {
    left  *Node
    right *Node
}

func countNodes(node *Node) int {
    if node == nil {
        // Your code here
    }
    // Your code here
}

func main() {
    node1 := &Node{}
    node2 := &Node{}
    node3 := &Node{}
    node4 := &Node{}
    node5 := &Node{}

    node1.left = node2
    node1.right = node3
    node2.left = node4
    node2.right = node5

    root := node1

    _ = root
}

Hint

Check if node is nil. If yes, return 0. Otherwise, return 1 plus recursive calls to countNodes on node.left and node.right.

4

Print the Total Number of Nodes

In the main function, call countNodes with root as argument and print the result using fmt.Println.

DSA Go

package main

import "fmt"

type Node struct {
    left  *Node
    right *Node
}

func countNodes(node *Node) int {
    if node == nil {
        return 0
    }
    return 1 + countNodes(node.left) + countNodes(node.right)
}

func main() {
    node1 := &Node{}
    node2 := &Node{}
    node3 := &Node{}
    node4 := &Node{}
    node5 := &Node{}

    node1.left = node2
    node1.right = node3
    node2.left = node4
    node2.right = node5

    root := node1

    // Your code here
}

Hint

Call countNodes(root) and print the result with fmt.Println.

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