Bird
Raised Fist0
Interview Preptree-dfseasyAmazonGoogle

Count Complete Tree Nodes

Choose your preparation mode4 modes available
▶
Steps
setup

Initialize root and start height computation

Start computing the height of the tree by initializing height counter and setting current node to root.

💡 Computing height by going down left children helps determine the number of levels in the tree.
Line:h = 0 while root: h += 1 root = root.left
💡 Height is the number of levels, which guides the binary search range for last level nodes.
📊
Count Complete Tree Nodes - Watch the Algorithm Execute, Step by Step
Watching each step reveals how the algorithm efficiently counts nodes without traversing every node, using tree properties and binary search.
Step 1/13
·Active fill★Answer cell
Current node: 1
123456
Current node: 1
123456
123456
123456
Current node: 2
123456
Return: true
123456
123456
Current node: 3
123456
Return: true
123456
123456
Current node: 3
123456
Return: false
123456
123456
Return: 6

Key Takeaways

✓ The algorithm efficiently counts nodes by leveraging the complete tree's height and binary search on the last level.

This insight is hard to see from code alone because it avoids naive traversal and uses tree properties cleverly.

✓ Binary search narrows down the last level nodes by checking existence through bitwise traversal.

Visualizing the traversal path for each index clarifies how the algorithm decides left or right moves.

✓ The final count combines nodes above the last level and the count of existing nodes found on the last level.

Understanding this sum is key to grasping why the algorithm returns the correct total node count.

Practice

(1/5)
1. Given the following Morris preorder traversal code, what is the final output list after running preorderTraversal on the tree below? Tree structure:

    1
   / \
  2   3
def preorderTraversal(root):
    result = []
    current = root
    while current:
        if current.left is None:
            result.append(current.val)
            current = current.right
        else:
            predecessor = current.left
            while predecessor.right and predecessor.right != current:
                predecessor = predecessor.right
            if predecessor.right is None:
                predecessor.right = current
                result.append(current.val)
                current = current.left
            else:
                predecessor.right = None
                current = current.right
    return result
easy
A. [2, 1, 3]
B. [1, 2, 3]
C. [1, 3, 2]
D. [3, 1, 2]

Solution

  1. Step 1: Trace first iteration with current=1

    Node 1 has left child 2, predecessor is 2 with no right child, set 2.right=1, append 1, move current=2.
  2. Step 2: Trace second iteration with current=2

    Node 2 has no left child, append 2, move current=2.right which points back to 1 (thread).
  3. Step 3: Detect thread at 2.right=1

    Since predecessor.right == current, reset 2.right=None, move current=1.right=3.
  4. Step 4: Trace current=3

    Node 3 has no left child, append 3, move current=3.right=None, loop ends.
  5. Final Answer:

    Option B -> Option B
  6. Quick Check:

    Output matches preorder traversal [1,2,3] [OK]
Hint: Morris preorder appends root before left subtree [OK]
Common Mistakes:
  • Appending nodes in wrong order
  • Not resetting threaded links
  • Confusing left and right child traversal
2. The following code attempts to check if a binary tree is balanced using iterative postorder traversal. Which line contains a subtle bug that can cause incorrect results on an empty tree or null root?
medium
A. Line 1: Missing check for empty root before traversal
B. Line 7: Incorrectly pushing node.left without null check
C. Line 12: Comparing last_visited with peek.right incorrectly
D. Line 16: Using abs difference without considering null children

Solution

  1. Step 1: Identify handling of empty tree

    The code does not check if root is None before starting traversal, which can cause errors or incorrect results.
  2. Step 2: Verify other lines

    Other lines handle null children safely using heights.get with default 0, and last_visited logic is correct.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Missing early return for empty root causes bug [OK]
Hint: Always check for empty root before traversal [OK]
Common Mistakes:
  • Forgetting to handle empty tree as balanced
  • Incorrectly comparing last_visited causing infinite loops
  • Not defaulting heights for null children
3. What is the time complexity of the optimal greedy postorder traversal solution for the Binary Tree Cameras problem, and why?
medium
A. O(n) because each node is visited once in postorder traversal
B. O(n^2) because each node's state depends on its children's states recursively
C. O(n log n) due to recursive calls and state checks at each node
D. O(h) where h is the height of the tree, since recursion depth equals height

Solution

  1. Step 1: Analyze traversal visits

    The algorithm visits each node exactly once in a postorder manner, processing left and right children before the node itself.
  2. Step 2: Consider work per node

    Each node's processing is O(1) -- checking children's states and updating counters.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Single DFS traversal over n nodes -> O(n) time [OK]
Hint: Each node processed once with constant work [OK]
Common Mistakes:
  • Assuming recursive calls multiply work to O(n^2)
  • Confusing recursion depth with total work
  • Thinking state checks add log n factor
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. 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