Count Total Nodes in Binary Tree in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a binary tree?

A binary tree is a structure where each node has at most two children called left and right child.

beginner

How do you count total nodes in a binary tree?

Count 1 for the current node plus the count of nodes in the left subtree and the right subtree.

beginner

What is the base case when counting nodes in a binary tree recursively?

When the node is null (no node), return 0 because there are no nodes to count.

intermediate

Why is recursion a good approach to count nodes in a binary tree?

Because each node's count depends on its children, recursion naturally breaks the problem into smaller parts.

intermediate

What is the time complexity of counting nodes in a binary tree?

O(n), where n is the number of nodes, because each node is visited once.

What should the function return when the current node is null?

A -1

B 1

C 0

D null

When the node is null, it means no node exists, so count is 0.

Which traversal method is used to count total nodes in a binary tree recursively?

A Inorder (left, node, right)

B Level order

C Postorder (left, right, node)

D Preorder (node, left, right)

Preorder traversal visits the node first, then counts left and right subtrees, suitable for counting nodes.

If a binary tree has 5 nodes, what will the count function return?

A 5

B 6

C 4

D 0

The function counts all nodes, so it returns 5 for 5 nodes.

What is the first step in counting nodes recursively?

A Count left subtree nodes

B Check if current node is null

C Count right subtree nodes

D Return total count

Always check if the current node is null to stop recursion.

What does the recursive call countNodes(node.left) do?

A Counts nodes in the left subtree

B Counts nodes in the right subtree

C Counts the current node

D Returns null

It counts all nodes in the left subtree of the current node.

Explain how recursion helps in counting total nodes in a binary tree.

Think about breaking the problem into smaller parts.

Describe the steps to count total nodes in a binary tree using a recursive function.

Focus on the order of operations in the function.

Practice

1. What does the function to count total nodes in a binary tree return when the tree is empty?

easy

A. -1

B. 1

C. 0

D. null

Solution

1. Step 1: Understand the base case for an empty tree

   When the binary tree is empty, there are no nodes to count, so the count should be zero.

2. Step 2: Confirm the function's return value for empty input

   The function should return 0 to indicate no nodes exist in the tree.

3. Final Answer:

   0 -> Option C

4. Quick Check:

   Empty tree node count = 0 [OK]

Hint: Empty tree always has zero nodes [OK]

Common Mistakes:

• Returning 1 for empty tree
• Returning null instead of 0
• Confusing empty tree with leaf node

2. Which of the following TypeScript function signatures correctly defines a function to count total nodes in a binary tree node structure?

easy

A. function countNodes(root: number): number

B. function countNodes(root: any): string

C. function countNodes(root: TreeNode): void

D. function countNodes(root: TreeNode | null): number

Solution

1. Step 1: Identify correct parameter type for binary tree root

   The root should be a TreeNode or null if the tree is empty.

2. Step 2: Confirm return type for count function

   The function returns a number representing total nodes, so return type must be number.

3. Final Answer:

   function countNodes(root: TreeNode | null): number -> Option D

4. Quick Check:

   Correct parameter and return types = function countNodes(root: TreeNode | null): number [OK]

Hint: Function must accept node or null and return number [OK]

Common Mistakes:

• Using wrong parameter type
• Returning void instead of number
• Returning string instead of number

3. Given the following binary tree code, what is the output of console.log(countNodes(root));?

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val: number) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

function countNodes(root: TreeNode | null): number {
  if (!root) return 0;
  return 1 + countNodes(root.left) + countNodes(root.right);
}

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

medium

A. 5

B. 6

C. 4

D. 3

Solution

1. Step 1: Count nodes in the tree structure

   The tree has nodes: 1 (root), 2 and 3 (children), 4 and 5 (children of 2). Total nodes = 5.

2. Step 2: Verify recursive count function output

   The function counts 1 for root plus counts of left and right subtrees, summing to 5.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   Total nodes counted = 5 [OK]

Hint: Count all nodes including root and children [OK]

Common Mistakes:

• Counting only leaf nodes
• Missing one subtree
• Off-by-one error in count

4. Identify the error in the following TypeScript function to count total nodes in a binary tree:

function countNodes(root: TreeNode | null): number {
  if (root === null) return 1;
  return 1 + countNodes(root.left) + countNodes(root.right);
}

medium

A. Function does not count the current node

B. Base case returns 1 instead of 0 for null

C. Missing return type annotation

D. Incorrect parameter type

Solution

1. Step 1: Check base case return value

   The base case returns 1 when root is null, which incorrectly counts non-existent nodes.

2. Step 2: Understand correct base case for counting nodes

   For null nodes, the count should be 0, not 1, to avoid overcounting.

3. Final Answer:

   Base case returns 1 instead of 0 for null -> Option B

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 counting current node
• Wrong parameter or return types

5. You want to count total nodes in a binary tree but only count nodes with even values. Which modification to the standard count function is correct?

function countEvenNodes(root: TreeNode | null): number {
  if (!root) return 0;
  const leftCount = countEvenNodes(root.left);
  const rightCount = countEvenNodes(root.right);
  // What to add here?
}

hard

A. return (root.val % 2 === 0 ? 1 : 0) + leftCount + rightCount;

B. return 1 + leftCount + rightCount;

C. return leftCount + rightCount;

D. return (root.val % 2 !== 0 ? 1 : 0) + leftCount + rightCount;

Solution

1. Step 1: Check node value for evenness

   Use modulo operator to check if root.val is even; if yes, count 1, else 0.

2. Step 2: Sum counts from left, right, and current node if even

   Add leftCount, rightCount, and 1 or 0 based on current node's evenness.

3. Final Answer:

   return (root.val % 2 === 0 ? 1 : 0) + leftCount + rightCount; -> Option A

4. Quick Check:

   Count only even nodes correctly [OK]

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

Common Mistakes:

• Counting all nodes regardless of value
• Counting odd nodes instead
• Forgetting to add left and right counts