Leetcode 222 - Count Complete Tree Nodes

post-thumb

Advance your Tech Career to new heights with Personalized Coaching from industry Experts at top companies.

Meet Your MAANG Coach Now

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.

Advance your Tech Career to new heights with Personalized Coaching from industry Experts at top companies.

Meet Your MAANG Coach Now

Related:

comments powered by Disqus