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

Count Total Nodes in Binary Tree

📖 Scenario: You are working with a simple family tree where each person can have up to two children. You want to find out how many people are in the family tree in total.

🎯 Goal: Build a Java program that creates a binary tree representing the family tree, then counts and prints the total number of nodes (people) in the tree.

📋 What You'll Learn

Create a binary tree with exactly 5 nodes with given values

Add a helper variable to hold the count of nodes

Write a recursive method called countNodes to count all nodes in the tree

Print the total count of nodes

💡 Why This Matters

🌍 Real World

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

💼 Career

Understanding tree traversal and counting nodes is a fundamental skill for software developers working with hierarchical data.

1

Create the Binary Tree

Create a class called Node with an integer data field and two Node references called left and right. Then create a binary tree with root node value 10, left child 5, right child 15, left child of left child 3, and right child of left child 7.

DSA Java

// Define Node class and create the binary tree with 5 nodes
// Your code here

Hint

Start by defining the Node class with data and two child references. Then create the root and its children as described.

2

Add a Variable to Hold the Count

Inside the Main class, create a static integer variable called totalNodes and set it to 0. This will hold the count of nodes in the tree.

DSA Java

class Node {
    int data;
    Node left, right;

    Node(int data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

public class Main {
    static int totalNodes = 0;

    public static void main(String[] args) {
        Node root = new Node(10);
        root.left = new Node(5);
        root.right = new Node(15);
        root.left.left = new Node(3);
        root.left.right = new Node(7);
    }
    // Your code here
}

Hint

Add a static variable totalNodes inside the Main class but outside the main method.

3

Write the Recursive Method to Count Nodes

Write a static method called countNodes that takes a Node parameter called root. It should return 0 if root is null. Otherwise, it should return 1 plus the count of nodes in the left subtree plus the count of nodes in the right subtree by calling itself recursively.

DSA Java

        totalNodes = countNodes(root);
        // Your code here
    static int countNodes(Node root) {
        if (root == null) {
            return 0;
        }
        return 1 + countNodes(root.left) + countNodes(root.right);

Hint

Use a simple recursive method that counts 1 for the current node and adds counts from left and right children.

4

Print the Total Number of Nodes

Add a System.out.println statement in the main method to print the text Total nodes in the tree: followed by the value of totalNodes.

DSA Java

Hint

Use System.out.println to print the message and the count variable.

Practice

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

easy

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

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

C. It counts only the nodes on the left subtree.

D. It counts only the nodes on the right subtree.

Solution

1. Step 1: Understand the node counting function

   The function visits every node in the tree, including root, left, and right children.

2. Step 2: Summarize the counting process

   It adds 1 for the current node plus counts from left and right subtrees recursively.

3. Final Answer:

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

4. Quick Check:

   Total nodes = all nodes in tree [OK]

Hint: Count every node visited including root and children [OK]

Common Mistakes:

• Counting only leaf nodes
• Ignoring one subtree
• Counting nodes twice

2. Which of the following is the correct Java method signature to count total nodes in a binary tree?

easy

A. public int countNodes(TreeNode root)

B. int countNodes()

C. void countNodes(TreeNode root)

D. public static void countNodes(TreeNode root)

Solution

1. Step 1: Identify method return type and parameters

   The method should return an integer count and accept the root node as parameter.

2. Step 2: Match correct Java syntax

   public int countNodes(TreeNode root) correctly declares public int countNodes(TreeNode root) which returns count.

3. Final Answer:

   public int countNodes(TreeNode root) -> Option A

4. Quick Check:

   Method returns int and takes root node [OK]

Hint: Method returns int and takes root node parameter [OK]

Common Mistakes:

• Using void return type
• Missing root parameter
• Incorrect access modifier

3. What is the output of the following code snippet?

class TreeNode {
  int val;
  TreeNode left, right;
  TreeNode(int val) { this.val = val; }
}

public class Main {
  public static int countNodes(TreeNode root) {
    if (root == null) return 0;
    return 1 + countNodes(root.left) + countNodes(root.right);
  }

  public static void main(String[] args) {
    TreeNode root = new TreeNode(1);
    root.left = new TreeNode(2);
    root.right = new TreeNode(3);
    root.left.left = new TreeNode(4);
    System.out.println(countNodes(root));
  }
}

medium

A. 3

B. 4

C. 5

D. 6

Solution

1. Step 1: Count nodes in the tree structure

   The tree has nodes: 1 (root), 2 (left), 3 (right), and 4 (left-left child). Total 4 nodes.

2. Step 2: Apply recursive countNodes function

   Function returns 1 + count of left subtree + count of right subtree = 4.

3. Final Answer:

   4 -> Option B

4. Quick Check:

   Nodes counted = 4 [OK]

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

Common Mistakes:

• Forgetting to count root node
• Miscounting null children
• Confusing node values with count

4. Find the error in this code to count total nodes in a binary tree:

public int countNodes(TreeNode root) {
  if (root == null) {
    return 1;
  }
  return 1 + countNodes(root.left) + countNodes(root.right);
}

medium

A. Does not count the current node

B. Missing base case for leaf nodes

C. Returns 1 when root is null instead of 0

D. Uses wrong method signature

Solution

1. Step 1: Check base case for null node

   Function returns 1 when root is null, which is incorrect; it should return 0.

2. Step 2: Verify counting logic

   The counting logic correctly adds 1 for the current node and recurses to both subtrees.

3. Final Answer:

   Returns 1 when root is null instead of 0 -> Option C

4. Quick Check:

   Base case must return 0 for null [OK]

Hint: Base case for null must return 0 nodes [OK]

Common Mistakes:

• Returning 1 for null node
• Not adding 1 for current node
• Incorrect recursion calls

5. Given a binary tree where each node has either 0 or 2 children, and the total nodes count is 15, how many leaf nodes does the tree have?

hard

A. 7

B. 15

C. 16

D. 8

Solution

1. Step 1: Use property of full binary tree

   In a full binary tree, number of leaf nodes = number of internal nodes + 1.

2. Step 2: Calculate leaf nodes from total nodes

   Total nodes = leaf nodes + internal nodes = 15. So leaf nodes = internal nodes + 1. Let internal nodes = x, then x + (x + 1) = 15 -> 2x + 1 = 15 -> 2x = 14 -> x = 7. Leaf nodes = 7 + 1 = 8.

3. Final Answer:

   8 -> Option D

4. Quick Check:

   Leaf nodes = internal nodes + 1 = 8 [OK]

Hint: In full binary tree, leaves = internal nodes + 1 [OK]

Common Mistakes:

• Confusing total nodes with leaf nodes
• Forgetting full binary tree property
• Incorrect algebra for leaf count