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

Challenge - 5 Problems

❓ Predict Output

intermediate

Count nodes in a simple binary tree

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

DSA C#

public class Node {
    public int Value;
    public Node Left, Right;
    public Node(int val) { Value = val; Left = Right = null; }
}

public class BinaryTree {
    public Node Root;
    public int CountNodes(Node node) {
        if (node == null) return 0;
        return 1 + CountNodes(node.Left) + CountNodes(node.Right);
    }
}

var tree = new BinaryTree();
tree.Root = new Node(1);
tree.Root.Left = new Node(2);
tree.Root.Right = new Node(3);
tree.Root.Left.Left = new Node(4);

int total = tree.CountNodes(tree.Root);
System.Console.WriteLine(total);

A 6

B 3

C 5

D 4

💡 Hint

Count each node including root and all children recursively.

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

❓ Predict Output

intermediate

Count nodes in a full binary tree

What will be printed after counting nodes in this full binary tree?

DSA C#

public class Node {
    public int Value;
    public Node Left, Right;
    public Node(int val) { Value = val; Left = Right = null; }
}

public class BinaryTree {
    public Node Root;
    public int CountNodes(Node node) {
        if (node == null) return 0;
        return 1 + CountNodes(node.Left) + CountNodes(node.Right);
    }
}

var tree = new BinaryTree();
tree.Root = new Node(10);
tree.Root.Left = new Node(20);
tree.Root.Right = new Node(30);
tree.Root.Left.Left = new Node(40);
tree.Root.Left.Right = new Node(50);
tree.Root.Right.Left = new Node(60);
tree.Root.Right.Right = new Node(70);

int total = tree.CountNodes(tree.Root);
System.Console.WriteLine(total);

A 6

B 8

C 7

D 5

💡 Hint

Count all nodes including root and all children.

The tree has 7 nodes: 10,20,30,40,50,60,70.

🧠 Conceptual

advanced

Understanding node counting complexity

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 recursive count.

The recursive function visits each node exactly once, so time complexity is linear in number of nodes.

🔧 Debug

advanced

Identify the bug in node counting code

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

DSA C#

public class Node {
    public int Value;
    public Node Left, Right;
    public Node(int val) { Value = val; Left = Right = null; }
}

public class BinaryTree {
    public Node Root;
    public int CountNodes(Node node) {
        if (node == null) return 0;
        return CountNodes(node.Left) + CountNodes(node.Right);
    }
}

var tree = new BinaryTree();
tree.Root = new Node(1);
tree.Root.Left = new Node(2);
int total = tree.CountNodes(tree.Root);
System.Console.WriteLine(total);

A Output is 0

B Output is 3

C StackOverflowException

D Compilation error

💡 Hint

Check if the current node is counted in the return statement.

The code misses counting the current node (no +1), so it outputs 0 instead of 2.

🚀 Application

expert

Count nodes in a binary tree with null nodes explicitly stored

Given a binary tree where null children are stored as explicit nodes with Value = -1, how many nodes will the count method return?

DSA C#

public class Node {
    public int Value;
    public Node Left, Right;
    public Node(int val) { Value = val; Left = Right = null; }
}

public class BinaryTree {
    public Node Root;
    public int CountNodes(Node node) {
        if (node == null) return 0;
        return 1 + CountNodes(node.Left) + CountNodes(node.Right);
    }
}

var tree = new BinaryTree();
tree.Root = new Node(1);
tree.Root.Left = new Node(-1); // explicit null
// Right child is null reference

int total = tree.CountNodes(tree.Root);
System.Console.WriteLine(total);

A 1

B 2

C 3

D 0

💡 Hint

Count all nodes including explicit null nodes.

The tree has root node (1) and one explicit null node (-1). Right child is null reference and not counted.

Practice

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

easy

A. Counts only the leaf nodes

B. Counts nodes only on the left subtree

C. Counts only the root node

D. Counts all nodes including root, left, and right children

Solution

1. Step 1: Understand the node counting concept

   The function counts every node in the tree, including root and all children.

2. Step 2: Differentiate from partial counts

   Counting only leaves or root ignores other nodes, so total count includes all nodes.

3. Final Answer:

   Counts all nodes including root, left, and right children -> Option D

4. Quick Check:

   Total nodes = all nodes in tree [OK]

Hint: Count every node visited in tree traversal [OK]

Common Mistakes:

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

2. Which of the following is the correct C# syntax to define a binary tree node class for counting nodes?

easy

A. public class Node { public int data; public Node left, right; }

B. class Node { int data; Node left, right; void count() {} }

C. public struct Node { int data; Node left; Node right; }

D. class Node { public int data; public Node left; private Node right; }

Solution

1. Step 1: Check class and member access

   public class Node { public int data; public Node left, right; } correctly defines a public class with public members for data and child nodes.

2. Step 2: Verify syntax correctness

   class Node { int data; Node left, right; void count() {} } misses access modifiers and method is irrelevant; C uses struct which is less common; D has private right node which restricts access.

3. Final Answer:

   public class Node { public int data; public Node left, right; } -> Option A

4. Quick Check:

   Correct class with public members [OK]

Hint: Use public class with public node references [OK]

Common Mistakes:

• Missing public keyword
• Using struct instead of class
• Private child nodes blocking access

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

class Node {
  public int data;
  public Node left, right;
  public Node(int val) { data = val; left = right = null; }
}

int CountNodes(Node root) {
  if (root == null) return 0;
  return 1 + CountNodes(root.left) + CountNodes(root.right);
}

// Tree:
//     1
//    / \
//   2   3
//  / 
// 4

Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);

Console.WriteLine(CountNodes(root));

medium

A. 4

B. 3

C. 5

D. 6

Solution

1. Step 1: Count nodes in the tree structure

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

2. Step 2: Apply recursive count function

   CountNodes returns 1 + left subtree count + right subtree count, summing to 4.

3. Final Answer:

   4 -> Option A

4. Quick Check:

   Nodes counted = 4 [OK]

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

Common Mistakes:

• Counting only children, missing root
• Miscounting null nodes
• Adding extra nodes

4. Identify the error in this C# method to count total nodes in a binary tree:

int CountNodes(Node root) {
  if (root == null) return 1;
  return CountNodes(root.left) + CountNodes(root.right);
}

medium

A. Returns 1 for null node instead of 0

B. Does not count the current root node

C. All of the above

D. Missing addition of 1 for current node

Solution

1. Step 1: Check base case return value

   Returning 1 for null node is incorrect; it should be 0 because null means no node.

2. Step 2: Check counting logic for current node

   Function does not add 1 for the current root node, so it misses counting it.

3. Step 3: Combine errors

   Both base case and missing addition cause wrong total count.

4. Final Answer:

   All of the above -> Option C

5. Quick Check:

   Base case and counting errors combined [OK]

Hint: Base case returns 0; add 1 for current node [OK]

Common Mistakes:

• Returning 1 for null node
• Not adding 1 for current node
• Ignoring base case correctness

5. Given a binary tree where some nodes have only one child, how would you modify the counting function to count only nodes that have at least one child?

hard

A. Count only leaf nodes

B. Count nodes where left or right child is not null, recursively

C. Count all nodes including leaves

D. Count nodes with both children null

Solution

1. Step 1: Define condition for counting nodes

   We want to count nodes that have at least one child, so check if left or right child is not null.

2. Step 2: Modify recursive function accordingly

   Recursively count nodes where left or right child exists, ignoring leaf nodes with no children.

3. Step 3: Implement logic

   Return 1 + counts of children if node has child; else 0 for leaf nodes.

4. Final Answer:

   Count nodes where left or right child is not null, recursively -> Option B

5. Quick Check:

   Count nodes with children only [OK]

Hint: Count nodes with at least one child only [OK]

Common Mistakes:

• Counting all nodes including leaves
• Counting only leaves
• Counting nodes with no children