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. 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 buggy iterative postorder traversal code:

def postorderTraversal(root):
    result = []
    stack = []
    last_visited = None
    current = root
    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        peek_node = stack[-1]
        if peek_node.right and last_visited == peek_node.right:
            current = peek_node.right
        else:
            result.append(peek_node.val)
            last_visited = stack.pop()
    return result

What is the bug in this code?

medium

A. The inner while loop should traverse right children instead of left

B. The condition should check if last_visited != peek_node.right, not == peek_node.right

C. The last_visited variable is never updated

D. The result list is appended before traversing the left subtree

Solution

1. Step 1: Examine condition for traversing right subtree

   Correct logic requires moving to right child if it exists and was not visited yet, so condition must be last_visited != peek_node.right.

2. Step 2: Identify effect of wrong condition

   Using last_visited == peek_node.right causes skipping right subtree traversal or infinite loops.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Fixing condition restores correct postorder traversal [OK]

Hint: Check last_visited != right child to avoid revisiting [OK]

Common Mistakes:

• Using == instead of !=
• Not updating last_visited
• Appending too early

4. Suppose you want to perform inorder traversal on a binary tree where nodes can have parent pointers but no left or right child pointers. Which approach correctly produces the inorder sequence without recursion or extra stack?

hard

A. Use Morris traversal by creating threads on parent pointers instead of child pointers.

B. Use breadth-first search since parent pointers allow level order traversal.

C. Use recursive traversal ignoring parent pointers, which will fail due to missing child links.

D. Use iterative traversal with a pointer to the current node and track previously visited node to decide traversal direction.

Solution

1. Step 1: Understand traversal constraints

   Without left/right child pointers, Morris traversal is not applicable since it relies on child links.

2. Step 2: Use parent pointers to simulate traversal

   By tracking current and previously visited nodes, we can move up or down the tree to simulate inorder traversal iteratively.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Tracking previous node enables correct traversal without extra space [OK]

Hint: Parent pointers + prev node tracking enable traversal [OK]

Common Mistakes:

• Trying to create threads on parent pointers
• Using recursion without child pointers
• Confusing BFS with inorder traversal

5. Suppose the binary tree nodes can have duplicate values, and you are given preorder and inorder traversals with duplicates. Which modification to the standard iterative approach is necessary to correctly reconstruct the tree?

hard

A. Use a hash map from value to a list of all indices in inorder, and track which index to use next during construction.

B. Ignore duplicates and build the tree as usual, since preorder and inorder uniquely identify the tree.

C. Sort the preorder array to remove duplicates before building the tree.

D. Use a brute force approach with array slicing to handle duplicates correctly.

Solution

1. Step 1: Understand the problem with duplicates

   Duplicates cause ambiguity in mapping values to inorder indices, breaking the unique root index lookup.

2. Step 2: Modify data structure

   Store all indices of each value in a list, and track which occurrence to use next to maintain correct subtree boundaries.

3. Step 3: Avoid naive approaches

   Ignoring duplicates or sorting breaks traversal properties; brute force is inefficient and unnecessary with proper tracking.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Tracking multiple indices per value resolves duplicate ambiguity [OK]

Hint: Track all inorder indices per value to handle duplicates [OK]

Common Mistakes:

• Assuming unique values always
• Sorting preorder breaks tree structure
• Using brute force causes inefficiency