Bird
Raised Fist0

The following code attempts to count nodes in a complete binary tree using the optimal approach. Identify the line containing the subtle bug that can cause incorrect counts for incomplete last levels.

medium🐞 Bug Identification Q14 of Q15
Tree: Depth-First Search - Count Complete Tree Nodes
The following code attempts to count nodes in a complete binary tree using the optimal approach. Identify the line containing the subtle bug that can cause incorrect counts for incomplete last levels.
def exists(idx, h, root):
    left, right = 0, 2**(h - 1) - 1
    for _ in range(h - 1):
        mid = (left + right) // 2
        if idx < mid:  # Bug here
            root = root.left
            right = mid
        else:
            root = root.right
            left = mid + 1
    return root is not null
ALine with 'if idx < mid:'
BLine with 'return root is not null'
CLine with 'root = root.right'
DLine with 'left, right = 0, 2**(h - 1) - 1'
Step-by-Step Solution
Solution:
  1. Step 1: Understand binary search condition

    The condition should be 'if idx <= mid' to correctly include mid index in left subtree.
  2. Step 2: Identify impact of bug

    Using 'idx < mid' excludes mid index from left subtree, causing incorrect traversal and wrong node existence checks.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Correct binary search must include mid index [OK]
Quick Trick: Binary search must use <= to include mid index [OK]
Common Mistakes:
MISTAKES
  • Using < instead of <= in binary search condition
Trap Explanation:
PITFALL
  • The off-by-one in condition looks subtle but breaks correctness on boundary indices.
Interviewer Note:
CONTEXT
  • Tests candidate's attention to detail in binary search conditions within tree traversal.
Master "Count Complete Tree Nodes" in Tree: Depth-First Search

3 interactive learning modes - each teaches the same concept differently

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions
More Tree: Depth-First Search Quizzes