Count Complete Tree Nodes

📋

Problem

Imagine you have a nearly full family tree and want to quickly count how many members are in it without visiting every single person.

Given the root of a complete binary tree, return the number of the nodes in the tree. A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

The number of nodes in the tree is in the range [0, 10^5].The tree is guaranteed to be complete.

Edge cases: Empty tree → 0Tree with only root node → 1Complete tree with last level half filled → correct count

</>

IDE

def countNodes(root: Optional[TreeNode]) -> int:public int countNodes(TreeNode root)int countNodes(TreeNode* root)function countNodes(root)

def countNodes(root):
    # Write your solution here
    pass

class Solution {
    public int countNodes(TreeNode root) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int countNodes(TreeNode* root) {
    // Write your solution here
    return 0;
}

function countNodes(root) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0Returning 0 for non-empty trees due to missing base case for root node.✅ Add base case: if root is None return 0; else return 1 + countNodes(root.left) + countNodes(root.right).

Wrong: n-1Off-by-one error missing counting the root node itself.✅ Ensure to add 1 for the current node before summing left and right subtree counts.

Wrong: Incorrect count for incomplete last levelAssuming last level is always full and counting nodes accordingly.✅ Count actual nodes by traversing the tree fully or using height checks, do not assume last level is full.

Wrong: TLEUsing naive DFS traversal on large input causing time limit exceeded.✅ Implement O((log n)^2) approach using tree height and perfect subtree checks or binary search on last level.

✓

Test Cases

Make sure your basic solution handles empty and single-node trees correctly.

Check your code for off-by-one errors and proper null node handling.

Consider optimizing your solution using tree height properties or binary search on last level.

t1_01basic

Input{"root":[1,2,3,4,5,6]}

Expected6

⏱ Performance - must finish in 2000ms

The tree has nodes 1 through 6 arranged as a complete binary tree, so the count is 6.

💡 Think about traversing all nodes to count them.

💡 Use a DFS or BFS traversal to visit every node exactly once.

💡 Return 1 plus counts of left and right subtrees recursively.

Why it failed: Returned count is incorrect because the traversal missed nodes or double counted. Fix by ensuring each node is counted exactly once via proper DFS.

✓ Correctly counts all nodes using a full traversal.

t1_02basic

Input{"root":[1,2,3,4,5,6,7]}

Expected7

⏱ Performance - must finish in 2000ms

A perfect complete binary tree with 7 nodes, all levels fully filled.

💡 Count all nodes by visiting each node once.

💡 Check that both left and right subtrees are counted recursively.

💡 Return 1 plus left subtree count plus right subtree count.

Why it failed: Incorrect count due to missing last node or incorrect recursion base case. Fix by returning 0 for null nodes and summing counts properly.

✓ Correctly counts all nodes including last level.

t2_01edge

Input{"root":[]}

Expected0

⏱ Performance - must finish in 2000ms

Empty tree has zero nodes.

💡 Check if the root is null or empty before counting.

💡 Return 0 immediately if tree is empty.

💡 Base case: if root is None, return 0.

Why it failed: Returned non-zero count for empty tree. Fix by adding base case to return 0 when root is null.

✓ Correctly returns 0 for empty tree.

t2_02edge

Input{"root":[1]}

Expected1

⏱ Performance - must finish in 2000ms

Tree with only root node has count 1.

💡 Check that single node trees return count 1.

💡 Base case: if root has no children, return 1.

💡 Return 1 plus counts of left and right subtrees (which are zero).

Why it failed: Returned 0 or incorrect count for single node tree. Fix by counting root node itself.

✓ Correctly counts single node tree as 1.

t2_03edge

Input{"root":[1,2,3,4,5]}

Expected5

⏱ Performance - must finish in 2000ms

Complete tree with last level half filled (nodes 4 and 5 present, 6 missing).

💡 Ensure counting includes all nodes present even if last level is incomplete.

💡 Traverse left and right subtrees fully to count all nodes.

💡 Return 1 plus counts of left and right subtrees recursively.

Why it failed: Incorrect count due to assuming last level is full. Fix by counting actual nodes present, not assuming perfect tree.

✓ Correctly counts nodes in incomplete last level.

t3_01corner

Input{"root":[1,2,3,4,5,6,7,8]}

Expected8

⏱ Performance - must finish in 2000ms

Complete tree with last level partially filled, testing off-by-one errors.

💡 Check that counting includes nodes on last level even if partially filled.

💡 Avoid off-by-one errors by counting all nodes reachable from root.

💡 Use recursion base case correctly and sum left and right subtree counts.

Why it failed: Off-by-one error: missed counting last node on last level. Fix by ensuring recursion counts all nodes, including last level partial nodes.

✓ Correctly counts all nodes including last level partial nodes.

t3_02corner

Input{"root":[1,2,3,4,null,6,7]}

Expected6

⏱ Performance - must finish in 2000ms

Complete tree with one missing node in last level (node 5 missing).

💡 Handle null children correctly in counting.

💡 Do not count null nodes as valid nodes.

💡 Return 0 for null nodes and sum counts of non-null children.

Why it failed: Incorrect count due to counting null children or skipping valid nodes. Fix by returning 0 for null nodes and counting only existing nodes.

✓ Correctly counts nodes ignoring null children.

t3_03corner

Input{"root":[1,2,3,4,5,6,null,8]}

Expected7

⏱ Performance - must finish in 2000ms

Complete tree with last level having only one child on leftmost side.

💡 Verify that nodes on leftmost side of last level are counted.

💡 Do not assume last level is full; count actual nodes.

💡 Traverse left subtree fully and count nodes recursively.

Why it failed: Missed counting leftmost child on last level due to incorrect traversal. Fix by traversing left subtree fully and counting all nodes.

✓ Correctly counts nodes including leftmost last level child.

t4_01performance

Input{"root":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100]}

Expectednull

⏱ Performance - must finish in 2000ms

Large complete binary tree with 100 nodes to test O((log n)^2) or O(n) solutions within 2 seconds.

💡 Use binary search on last level or height-based checks to optimize counting.

💡 Avoid naive DFS that visits every node for large n.

💡 Implement O((log n)^2) approach using tree height and perfect subtree checks.

Why it failed: TLE due to O(n) brute force traversal on large input. Fix by implementing height-based or binary search approach to reduce complexity.

✓ Efficient solution runs within time limit using O((log n)^2) complexity.

Practice

1. You need to determine if a binary tree is height-balanced, meaning the heights of the two child subtrees of any node never differ by more than one. Which approach guarantees an optimal O(n) time solution without redundant height computations?

easy

A. Use a top-down recursive approach that checks balance only at the root node.

B. Compute height for each node separately and check balance at each node recursively.

C. Perform a breadth-first traversal and check balance by comparing subtree sizes at each level.

D. Use a postorder traversal that returns height and balance status simultaneously, stopping early if imbalance is found.

Solution

1. Step 1: Understand the problem constraints

   The problem requires checking balance at every node efficiently without recomputing heights multiple times.

2. Step 2: Identify the approach that avoids redundant work

   Postorder traversal that returns both height and balance status in one pass allows early exit on imbalance and avoids repeated height calculations.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Postorder traversal with early exit is O(n) and avoids recomputation [OK]

Hint: Postorder traversal with early exit avoids repeated height calls [OK]

Common Mistakes:

• Checking balance only at root misses subtree imbalances
• Computing height separately for each node causes O(n²) time
• Using BFS to check balance is incorrect as balance depends on subtree heights

2. Given the following code snippet for building a tree from inorder and postorder traversals, what is the value of inorder_index after processing the first iteration of the for-loop when inorder = [9,3,15,20,7] and postorder = [9,15,7,20,3]?

easy

A. 4

B. 2

C. 1

D. 3

Solution

1. Step 1: Initialize variables

   inorder_index starts at 4 (last index of inorder). The root is 3 (postorder[-1]).

2. Step 2: First iteration (i=3, node_val=20)

   top.val=3 != inorder[4]=7, so attach 20 as right child, stack grows, inorder_index stays 4.

3. Step 3: Second iteration (i=2, node_val=7)

   top.val=20 != inorder[4]=7 is false, so enter else: pop stack while top.val == inorder[inorder_index]. 20 != 7, so no pop, attach 7 as right child, stack grows, inorder_index stays 4.

4. Step 4: Third iteration (i=1, node_val=15)

   top.val=7 == inorder[4]=7, pop 7, inorder_index=3; top.val=20 == inorder[3]=20, pop 20, inorder_index=2; top.val=3 != inorder[2]=15, stop popping. Attach 15 as left child, stack grows.

5. Final Answer:

   Option D -> Option D

6. Quick Check:

   inorder_index decremented twice after popping 7 and 20 [OK]

Hint: inorder_index decrements only when popping matching nodes [OK]

Common Mistakes:

• Off-by-one error in inorder_index update
• Confusing when to pop stack
• Misreading top.val vs inorder[inorder_index]

3. Given a binary tree, you need to find the length of the longest path between any two nodes in the tree. This path may or may not pass through the root. Which approach guarantees an optimal solution to this problem?

easy

A. Perform a postorder traversal computing heights and update the diameter at each node using recursion with a global variable.

B. Apply dynamic programming with memoization on node pairs to find longest paths.

C. Use a greedy traversal that always chooses the deeper subtree at each node.

D. Calculate the height of the tree and multiply by two to estimate the diameter.

Solution

1. Step 1: Understand the problem requires the longest path between any two nodes, not necessarily passing through root.

   The diameter can be found by checking the sum of left and right subtree heights at every node.

2. Step 2: Recognize that a postorder traversal with recursion and a global variable to track diameter updates at each node ensures all paths are considered.

   This approach visits each node once, updating the diameter with left_height + right_height.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Postorder traversal with global diameter update covers all nodes [OK]

Hint: Diameter updates at every node, not just root [OK]

Common Mistakes:

• Thinking diameter must pass through root
• Using greedy to pick deeper subtree only
• Confusing diameter with twice height

4. Consider this modified Morris inorder traversal code snippet. Which line contains a subtle bug that can cause infinite loops or incorrect output on some trees?

def inorderTraversal(root):
    result = []
    current = root
    while current:
        if not current.left:
            result.append(current.val)
            current = current.right
        else:
            predecessor = current.left
            while predecessor.right and predecessor.right != current:
                predecessor = predecessor.right
            if not predecessor.right:
                predecessor.right = current  # create thread
                current = current.left
            else:
                # BUG: missing line to remove thread
                result.append(current.val)
                current = current.right
    return result

medium

A. Missing line resetting predecessor.right = None to remove thread

B. Line moving current to current.left after creating thread

C. Line appending current.val after detecting thread

D. Line setting predecessor.right = current (creating thread)

Solution

1. Step 1: Identify thread removal step

   Morris traversal requires removing the temporary thread by setting predecessor.right = None after visiting the node.

2. Step 2: Locate missing removal

   The code lacks the line resetting predecessor.right = None, causing infinite loops or corrupted tree structure.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Without removing thread, traversal loops endlessly [OK]

Hint: Always remove threads to restore tree [OK]

Common Mistakes:

• Forgetting to remove thread
• Appending node before removing thread
• Incorrectly creating thread

5. Suppose the problem is modified so that paths can move both downwards and upwards (i.e., any connected path in the tree, not necessarily parent-to-child). Which of the following changes to the algorithm is necessary to correctly count all such paths?

hard

A. Convert the tree to an undirected graph and use DFS from every node with prefix sums, resetting counts after each start.

B. Use the brute force approach checking all paths from every node without prefix sums.

C. Use the same prefix sum DFS approach but run it twice: once from root down and once from leaves up.

D. Modify the prefix sum map to store sums for paths in both directions simultaneously during one DFS.

Solution

1. Step 1: Understand path direction relaxation

   Allowing upward and downward moves means paths are any connected sequences, not just parent-to-child.

2. Step 2: Model tree as undirected graph and run DFS from every node

   To count all paths, treat tree as undirected graph and run DFS from each node, using prefix sums and resetting counts to avoid cross-branch contamination.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Undirected DFS from every node with prefix sums counts all connected paths [OK]

Hint: Undirected graph DFS needed for arbitrary path directions [OK]

Common Mistakes:

• Trying to reuse one-directional prefix sum DFS without modification
• Assuming running DFS twice covers all paths
• Trying to store both directions in one prefix sum map