Bird
Raised Fist0
Interview Preptree-dfseasyAmazonGoogle

Count Complete Tree Nodes

Choose your preparation mode4 modes available
📋
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
}
0/9
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
t1_01basic
Input{"root":[1,2,3,4,5,6]}
Expected6

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

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

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

t2_01edge
Input{"root":[]}
Expected0

Empty tree has zero nodes.

t2_02edge
Input{"root":[1]}
Expected1

Tree with only root node has count 1.

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

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

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

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

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

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

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

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

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]}
⏱ 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.

Practice

(1/5)
1. Consider the following code snippet implementing the optimal DFS approach for the Path Sum problem. Given the tree below and targetSum = 22, what is the return value of the function call hasPathSum(root, 22)? Tree structure: - root = TreeNode(5) - root.left = TreeNode(4) - root.right = TreeNode(8) - root.left.left = TreeNode(11) - root.left.left.left = TreeNode(7) - root.left.left.right = TreeNode(2) - root.right.left = TreeNode(13) - root.right.right = TreeNode(4) - root.right.right.right = TreeNode(1)
def hasPathSum(root: Optional[TreeNode], targetSum: int) -> bool:
    def dfs(node, curr_sum):
        if not node:
            return False
        curr_sum += node.val
        if not node.left and not node.right:
            return curr_sum == targetSum
        return dfs(node.left, curr_sum) or dfs(node.right, curr_sum)
    return dfs(root, 0)
easy
A. True
B. False
C. Raises an exception due to null pointer
D. Returns True only if the root value equals targetSum

Solution

  1. Step 1: Trace the path sums

    Check root-to-leaf paths: - 5↔4↔11↔7 = 27 - 5↔4↔11↔2 = 22 (matches targetSum) - 5↔8↔13 = 26 - 5↔8↔4↔1 = 18 Since one path sums to 22, the function returns True.
  2. Step 2: Confirm code logic

    The DFS returns True as soon as it finds the matching path sum at a leaf node.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Path 5↔4↔11↔2 sums to 22, so return True [OK]
Hint: Check all root-to-leaf paths, not just partial sums [OK]
Common Mistakes:
  • Stopping at non-leaf nodes
  • Ignoring leaf node condition
2. What is the time complexity of the brute force approach that separately computes height for each node to check if a binary tree is balanced?
medium
A. O(n^2)
B. O(n)
C. O(n log n)
D. O(n h) where h is tree height

Solution

  1. Step 1: Analyze height computation calls

    Height is computed recursively for each node, and each height call traverses subtree nodes.
  2. Step 2: Calculate total calls

    For n nodes, height is called at each node, and each call can take O(n) in worst case, leading to O(n^2) total time.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Repeated height calls cause quadratic time [OK]
Hint: Repeated height calls cause O(n²) time [OK]
Common Mistakes:
  • Assuming height calls are O(1) leading to O(n) time
  • Confusing height with depth or tree height h
  • Thinking O(n log n) due to balanced tree assumption
3. 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
4. What is the time complexity of the optimized recursive solution that uses a hash map for index lookup when constructing a binary tree from inorder and postorder traversals of size n?
medium
A. O(n) because each node is processed once and index lookup is O(1)
B. O(n^2) due to repeated slicing of arrays
C. O(n log n) because of balanced tree recursion depth
D. O(n) but with O(n) auxiliary space for recursion stack and hash map

Solution

  1. Step 1: Analyze time complexity

    Using a hash map avoids repeated linear searches, so each node is processed once -> O(n) time.
  2. Step 2: Analyze space complexity

    Hash map stores n elements, recursion stack can be up to O(n) in skewed trees, so total auxiliary space is O(n).
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Time is O(n), space includes recursion stack and hash map [OK]
Hint: Hash map reduces search to O(1), recursion stack adds O(n) space [OK]
Common Mistakes:
  • Assuming slicing causes O(n^2) time
  • Ignoring recursion stack space
  • Confusing balanced tree depth with complexity
5. The following code attempts to flatten a binary tree to a linked list in-place. Identify the bug that causes the flattened list to still have left child pointers, violating the problem requirements.
medium
A. Missing line to set root.left = None
B. Line: flatten(root.left)
C. Line: root.right = prev
D. Line: flatten(root.right)

Solution

  1. Step 1: Review rewiring steps

    The code sets root.right = prev but does not set root.left = None, so left pointers remain.
  2. Step 2: Identify missing step

    Setting root.left = None is required to ensure the flattened list has no left children.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Left pointers must be nullified to meet problem constraints [OK]
Hint: Always set root.left = None when flattening [OK]
Common Mistakes:
  • Forgetting to nullify left pointers
  • Misordering recursive calls causing wrong sequence
  • Losing subtree references by incorrect rewiring
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard