Count Complete Tree Nodes

▶

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.

setup

Check if tree is empty or height is 1

Check if root is None or height is 1 to handle trivial cases.

💡 If tree is empty or has only one node, counting is trivial and we can return immediately.

Line:

if not root:
    return 0
if h == 1:
    return 1

💡 Since height is 3, the tree has multiple levels and we need to perform binary search on the last level.

setup

Initialize binary search boundaries for last level

Set left and right pointers to cover all possible node indices on the last level.

💡 The last level can have up to 2^(h-1) nodes indexed from 0 to 2^(h-1)-1.

Line:

left, right = 0, 2**(h - 1) - 1

💡 We will binary search in this range to find the last existing node index on the last level.

compare

Binary search iteration 1: Calculate mid index

Calculate mid index as (left + right) // 2 to check if node exists at this index.

💡 Mid index splits the search space to check node existence efficiently.

Line:

mid = (left + right) // 2

💡 Mid is 1, so we will check if node at index 1 exists on last level.

traverse

Check existence of node at index 1 on last level

Traverse from root to check if node at index 1 exists on last level by following bits of index.

💡 Node existence is checked by interpreting index bits to decide left or right moves.

Line:

exists(mid, h, root)

💡 Node at index 1 exists, so we will move left boundary up.

shrink

Update binary search left boundary after node exists

Since node at mid exists, move left boundary to mid + 1 to search higher indices.

💡 Moving left boundary up narrows search to nodes after mid index.

Line:

if exists(mid, h, root):
    left = mid + 1

💡 We know nodes up to index 1 exist, so next search is from index 2 to 3.

compare

Binary search iteration 2: Calculate mid index

Calculate new mid index as (left + right) // 2 for next existence check.

💡 Mid index recalculates to narrow down the search space.

Line:

mid = (left + right) // 2

💡 Mid is 2, so we check node at index 2 on last level.

traverse

Check existence of node at index 2 on last level

Traverse from root to check if node at index 2 exists on last level by following bits of index.

💡 Checking node existence by interpreting index bits guides traversal left or right.

Line:

exists(mid, h, root)

💡 Node at index 2 exists, so we will move left boundary up again.

shrink

Update binary search left boundary after node exists

Since node at mid exists, move left boundary to mid + 1 to search higher indices.

💡 Moving left boundary up narrows search to nodes after mid index.

Line:

if exists(mid, h, root):
    left = mid + 1

💡 Nodes up to index 2 exist, so next search is index 3 to 3.

compare

Binary search iteration 3: Calculate mid index

Calculate mid index as (left + right) // 2 for last existence check.

💡 Mid index recalculates to check the last possible node index.

Line:

mid = (left + right) // 2

💡 Mid is 3, so we check node at index 3 on last level.

traverse

Check existence of node at index 3 on last level

Traverse from root to check if node at index 3 exists on last level by following bits of index.

💡 Checking node existence by interpreting index bits guides traversal left or right.

Line:

exists(mid, h, root)

💡 Node at index 3 does not exist, so we will move right boundary down.

shrink

Update binary search right boundary after node does not exist

Since node at mid does not exist, move right boundary to mid - 1 to search lower indices.

💡 Moving right boundary down narrows search to nodes before mid index.

Line:

else:
    right = mid - 1

💡 Nodes exist up to index 2, so binary search ends with left=3, right=2.

reconstruct

Calculate total nodes count

Calculate total nodes as nodes above last level plus count of nodes found on last level.

💡 Nodes above last level are 2^(h-1)-1, add left boundary as count of last level nodes.

Line:

return (2**(h - 1) - 1) + left

💡 Total nodes count is 3 + 3 = 6 for this tree.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def height(root):
    h = 0  # STEP 1
    while root:  # STEP 1
        h += 1  # STEP 1
        root = root.left  # STEP 1
    return h

def exists(idx, h, root):
    left, right = 0, 2**(h - 1) - 1  # STEP 5
    for _ in range(h - 1):  # STEP 5 loop
        mid = (left + right) // 2  # STEP 5
        if idx <= mid:  # STEP 5 decision
            root = root.left  # STEP 5
            right = mid  # STEP 5
        else:
            root = root.right  # STEP 5
            left = mid + 1  # STEP 5
    return root is not None  # STEP 5

def countNodes(root):
    if not root:  # STEP 2
        return 0
    h = height(root)  # STEP 1
    if h == 1:  # STEP 2
        return 1
    left, right = 0, 2**(h - 1) - 1  # STEP 3
    while left <= right:  # STEP 4 loop
        mid = (left + right) // 2  # STEP 4
        if exists(mid, h, root):  # STEP 5
            left = mid + 1  # STEP 6
        else:
            right = mid - 1  # STEP 12
    return (2**(h - 1) - 1) + left  # STEP 13

if __name__ == '__main__':
    root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, TreeNode(6), None))
    print(countNodes(root))  # Output: 6

📊

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.

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. 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. Consider the following iterative DFS code snippet for counting paths with sum equal to targetSum in a binary tree. Given the tree with root value 1, left child 2, right child 3, and targetSum = 3, what is the final value of result after the loop finishes?

class Solution:
    def pathSum(self, root, targetSum):
        if not root:
            return 0
        prefix_counts = {0: 1}
        result = 0
        stack = [(root, 0, False)]  # node, current_sum, visited_children

        while stack:
            node, current_sum, visited = stack.pop()
            if node is None:
                continue
            if not visited:
                current_sum += node.val
                result += prefix_counts.get(current_sum - targetSum, 0)
                prefix_counts[current_sum] = prefix_counts.get(current_sum, 0) + 1
                stack.append((node, current_sum, True))  # Mark node as visited
                stack.append((node.right, current_sum, False))
                stack.append((node.left, current_sum, False))
            else:
                prefix_counts[current_sum] -= 1

        return result

easy

A. 1

B. 0

C. 3

D. 2

Solution

1. Step 1: Trace initial stack and prefix_counts

   Start with stack=[(1,0,False)], prefix_counts={0:1}, result=0.

2. Step 2: Process nodes and update result

   Paths summing to 3 are: (1->2) and (3) alone, total 2 paths counted.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Two valid paths found matching target sum [OK]

Hint: Count paths by prefix sums during DFS traversal [OK]

Common Mistakes:

• Missing the single node path (3)
• Double counting paths due to prefix_counts not decremented
• Off-by-one in updating result

3. You are given a binary tree and a target sum. You need to determine if there exists a root-to-leaf path such that adding up all the values along the path equals the target sum. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Depth-first search (DFS) with early stopping upon finding a valid path

B. Greedy traversal choosing the child with the closest value to the target sum

C. Dynamic programming with memoization of partial sums at each node

D. Breadth-first search (BFS) exploring all paths level by level

Solution

1. Step 1: Understand the problem constraints

   The problem requires checking if any root-to-leaf path sums to the target. This naturally fits a tree traversal pattern.

2. Step 2: Identify the best approach

   DFS with early stopping is optimal because it explores paths deeply and stops as soon as a valid path is found, avoiding unnecessary work.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DFS explores paths fully and stops early when possible [OK]

Hint: Early stopping DFS avoids unnecessary traversal [OK]

Common Mistakes:

• Believing greedy approach works for sums
• Confusing BFS with DFS for path sums

4. 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

5. Consider this modified code snippet for the Binary Tree Cameras problem. Which line contains the subtle bug that causes incorrect camera placement?

medium

A. Line returning COVERED_NO_CAM after placing a camera instead of HAS_CAM

B. Line returning NOT_COVERED at the end of dfs

C. Line checking if dfs(root) == NOT_COVERED after traversal

D. Line returning COVERED_NO_CAM when node is null

Solution

1. Step 1: Identify camera placement logic

   When a child is NOT_COVERED, a camera must be placed at current node and dfs must return HAS_CAM to indicate camera presence.

2. Step 2: Locate incorrect return

   The code returns COVERED_NO_CAM after placing a camera, which falsely signals no camera here, causing parents to misinterpret coverage.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Returning HAS_CAM is essential after placing a camera [OK]

Hint: Return HAS_CAM after placing camera to signal coverage [OK]

Common Mistakes:

• Returning COVERED_NO_CAM instead of HAS_CAM after camera placement
• Forgetting to add camera if root uncovered
• Mixing coverage states in conditions