Leetcode 222 - Count Complete Tree Nodes

Understanding the problem

The problem statement on LeetCode reads as follows:

Given a complete binary tree, count the number of nodes.

Note:

Definition of a complete binary tree from Wikipedia: In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

Example 1:

Input: root = [1,2,3,4,5,6]

Output: 6

Plan your solution

We can use binary search to find the number of nodes in the tree because the tree is a complete binary tree, which means that the nodes are filled in level by level from left to right. This means that we can use the height of the left subtree to calculate the number of nodes in the tree using binary search.

First, we calculate the height of the left subtree. Then, we set the left and right pointers to the minimum and maximum possible values for the index of a node in the tree (1 and 2^h-1, respectively). We use the exists() function to check if the node at index mid exists in the tree. If it exists, we move the left pointer.

Implement your solution

Now that we have a plan, let’s implement it in Python.

def countNodes(root):
    # Base case: if the root is None, return 0
    if not root:
        return 0

    # Calculate the height of the left subtree
    h = 0
    node = root
    while node:
        h += 1
        node = node.left

    # Calculate the number of nodes in the tree using binary search
    left, right = 1, 2**h - 1
    while left <= right:
        # Calculate the middle point between the left and right pointers
        mid = (left + right) // 2
        # Check if the node at index mid exists in the tree
        if exists(root, h, mid):
            # If it exists, move the left pointer to the middle point
            left = mid + 1
        else:
            # If it does not exist, move the right pointer to the middle point
            right = mid - 1

    # Return the number of nodes
    return 2**h - 1 + left - 1

def exists(root, h, index):
    # Base case: if the root is None, return False
    if not root:
        return False

    # Calculate the height of the right subtree
    h_right = 0
    node = root
    while node:
        h_right += 1
        node = node.right

    # If the height of the right subtree is equal to h-1, it means that the left subtree is a full tree
    if h_right == h - 1:
        # If the index is in the left subtree, recurse on the left child
        if index <= 2**(h-1) - 1:
            return exists(root.left, h-1, index)
        # If the index is in the right subtree, recurse on the right child
        else:
            return exists(root.right, h-1, index - 2**(h-1))
    # If the height of the right subtree is less than h-1, it means that the right subtree is a full tree
    else:
        # If the index is in the left subtree, recurse on the left child
        if index <= 2**h_right - 1:
            return exists(root.left, h_right, index)
        # If the index is in the right subtree, recurse on the right child
        else:
            return exists(root.right, h_right, index - 2**h_right)

Testing your solution

Testing is an important step in the software development process, as it helps ensure that your code is correct and works as intended. In the case of the “Count Complete Tree Nodes” problem, we can test our solution by running a series of test cases that cover different scenarios and edge cases.

For example, we can test our solution with a tree that has only a root node, a tree that has a root node and two children, a tree that has a root node and four children, and so on. We can also test our solution with trees that have different numbers of nodes at each level. By running a variety of test cases, we can gain confidence that our solution is correct and will work for all inputs.

Related:

• longest arithmetic subsequence
• count negative numbers in a sorted matrix
• unique binary search trees

Related Posts

• Leetcode 424 - Longest Repeating Character Replacement
• Two Sum and Its Variants
• Leetcode 1004 - Max Consecutive Ones III
• Leetcode 1027 - Longest Arithmetic Subsequence
• Question 1299 on leetcode
• Leetcode 240 - Search a 2D Matrix II
• Leetcode 1351 - Count Negative Numbers in a Sorted Matrix
• Leetcode 239 - Sliding Window Maximum
• Leetcode 209 - Minimum Size Subarray Sum
• LeetCode 230 - Kth Smallest Element in a BST with Code
• advanced-applications-of-binary-search
• Leetcode 96 - Unique Binary Search Trees
• Leetcode 540 - Single Element in a Sorted Array
• Leetcode 1283 - Find the Smallest Divisor Given a Threshold
• Leetcode 74 - Search a 2D Matrix
• Leetcode 300 - Longest Increasing Subsequence
• Blazingly fast solution to LeetCode #1342 - Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold (Cross-post from r/SoftwareEngineering)
• Leetcode 704 - Binary Search
• Leetcode 643 - Maximum Average Subarray I
• LeetCode - Two Sum Solution with Code
• a-binary-search-template
• Leetcode 1358 - Number of Substrings Containing All Three Characters
• Data structures and Algorithm Interview Questions
• Leetcode 33 - Search in Rotated Sorted Array
• Leetcode 1151 - Minimum Swaps to Group All 1’s Together