Count Total Nodes in Binary Tree in DSA Javascript - 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 Javascript

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

function countNodes(root) {
  if (!root) return 0;
  return 1 + countNodes(root.left) + countNodes(root.right);
}

const root = new Node(10);
root.left = new Node(5);
root.right = new Node(15);
root.left.left = new Node(3);

console.log(countNodes(root));

A 4

B 3

C 5

D 6

💡 Hint

Count each node including root, left child, right child, and left-left child.

The tree has 4 nodes: root (10), left (5), right (15), and left-left (3). The function counts all nodes recursively.

❓ Predict Output

intermediate

Count nodes in an empty tree

What is the output when counting nodes in an empty binary tree?

DSA Javascript

function countNodes(root) {
  if (!root) return 0;
  return 1 + countNodes(root.left) + countNodes(root.right);
}

const root = null;
console.log(countNodes(root));

A 0

B null

C 1

D undefined

💡 Hint

An empty tree has no nodes.

The function returns 0 immediately when root is null, meaning no nodes exist.

❓ Predict Output

advanced

Count nodes in a full binary tree

What is the output of counting nodes in this full binary tree?

DSA Javascript

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

function countNodes(root) {
  if (!root) return 0;
  return 1 + countNodes(root.left) + countNodes(root.right);
}

const root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);

console.log(countNodes(root));

A 8

B 5

C 6

D 7

💡 Hint

Count all nodes including root, its two children, and their children.

The tree has 7 nodes: root (1), two children (2,3), and four grandchildren (4,5,6,7).

❓ Predict Output

advanced

Count nodes in an unbalanced binary tree

What is the output of counting nodes in this unbalanced binary tree?

DSA Javascript

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

function countNodes(root) {
  if (!root) return 0;
  return 1 + countNodes(root.left) + countNodes(root.right);
}

const root = new Node(10);
root.left = new Node(5);
root.left.left = new Node(3);
root.left.left.left = new Node(1);
root.right = new Node(15);

console.log(countNodes(root));

A 4

B 5

C 6

D 3

💡 Hint

Count all nodes including the deep left branch.

The tree has 5 nodes: 10, 5, 3, 1 on the left side and 15 on the right.

🧠 Conceptual

expert

Time complexity of counting nodes in binary tree

What is the time complexity of counting total nodes in a binary tree using a recursive function that visits each node once?

A O(n^2), where n is the number of nodes

B O(log n), where n is the number of nodes

C O(n), where n is the number of nodes

D O(1), constant time

💡 Hint

The function visits every node exactly once.

Since the function visits each node once, the time grows linearly with the number of nodes.

Practice

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

easy

A. It returns the total number of nodes in the tree.

B. It returns the height of the tree.

C. It returns the sum of all node values.

D. It returns the number of leaf nodes only.

Solution

1. Step 1: Understand the function's purpose

   The function is designed to count every node in the binary tree, including root, internal, and leaf nodes.

2. Step 2: Differentiate from other tree properties

   Counting nodes is different from calculating height, sum of values, or counting leaves, which are other tree properties.

3. Final Answer:

   It returns the total number of nodes in the tree. -> Option A

4. Quick Check:

   Counting nodes = total nodes [OK]

Hint: Count all nodes, not just leaves or height [OK]

Common Mistakes:

• Confusing node count with tree height
• Counting only leaf nodes
• Summing node values instead of counting

2. Which of the following is the correct base case syntax in JavaScript for counting nodes in a binary tree recursively?

easy

A. if (node == undefined) return 1;

B. if (node === null) return 0;

C. if (node === undefined) return null;

D. if (node === null) return null;

Solution

1. Step 1: Identify the base case for recursion

   When the node is null (no node), the count should be zero because there is no node to count.

2. Step 2: Check correct JavaScript syntax

   Using strict equality (===) to check for null and returning 0 is the correct approach.

3. Final Answer:

   if (node === null) return 0; -> Option B

4. Quick Check:

   Base case null node returns 0 [OK]

Hint: Base case returns 0 for null nodes [OK]

Common Mistakes:

• Returning 1 for null nodes
• Using == instead of ===
• Returning null instead of 0

3. What is the output of the following code snippet counting nodes in a binary tree?

class Node {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

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

function countNodes(node) {
  if (node === null) return 0;
  return 1 + countNodes(node.left) + countNodes(node.right);
}

console.log(countNodes(root));

medium

A. 2

B. 3

C. 5

D. 4

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 nodes = 4.

2. Step 2: Apply recursive countNodes function

   Function counts 1 for current node plus counts of left and right subtrees recursively, resulting in 4.

3. Final Answer:

   4 -> Option D

4. Quick Check:

   Nodes counted = 4 [OK]

Hint: Add 1 + left subtree + right subtree counts [OK]

Common Mistakes:

• Forgetting to count the root node
• Miscounting child nodes
• Confusing left and right subtree counts

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

function countNodes(node) {
  if (node == null) return 1;
  return 1 + countNodes(node.left) + countNodes(node.right);
}

medium

A. Base case returns 1 instead of 0 for null node.

B. Missing addition of 1 for current node in return statement.

C. Using == instead of === causes error.

D. Function should return node.val instead of count.

Solution

1. Step 1: Check base case return value

   Base case returns 1 when node is null, which incorrectly counts non-existent nodes.

2. Step 2: Understand correct base case

   Base case should return 0 for null nodes because they do not exist and should not add to count.

3. Final Answer:

   Base case returns 1 instead of 0 for null node. -> Option A

4. Quick Check:

   Null node count must be 0 [OK]

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

Common Mistakes:

• Returning 1 for null nodes
• Not adding 1 for current node
• Confusing equality operators

5. Given a binary tree where some nodes have only one child, how would you modify the countNodes function to count all nodes correctly even if some children are missing?

function countNodes(node) {
  if (node === null) return 0;
  return 1 + countNodes(node.left) + countNodes(node.right);
}

hard

A. Add a global counter variable outside the function.

B. Add checks to count only nodes with two children.

C. No change needed; function already counts all nodes correctly.

D. Change base case to return 1 for null nodes.

Solution

1. Step 1: Analyze current function behavior

   The function returns 0 for null nodes and adds 1 for each existing node plus counts of left and right children recursively.

2. Step 2: Confirm it handles missing children

   Since null children return 0, missing children do not add to count, so all existing nodes are counted correctly.

3. Final Answer:

   No change needed; function already counts all nodes correctly. -> Option C

4. Quick Check:

   Function counts all nodes including those with missing children [OK]

Hint: Null children return 0, so all nodes count correctly [OK]

Common Mistakes:

• Thinking missing children need special counting
• Changing base case incorrectly
• Using global counters unnecessarily