Jobs

Interviews

Discussions

Count Complete Tree Nodes

Easy

Asked by:

More companies

55 views

Topics:

TreesBinary SearchRecursion

Given the root of a complete binary tree, return the number of the nodes in the tree.

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

Design an algorithm that runs in less than O(n) time complexity.

Example 1:

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

Example 2:

Input: root = []
Output: 0

Example 3:

Input: root = [1]
Output: 1

Constraints:

The number of nodes in the tree is in the range [0, 5 * 10⁴].
0 <= Node.val <= 5 * 10⁴
The tree is guaranteed to be complete.

Try coding it in LeetCode

Count Complete Tree Nodes

Easy

Asked by:

55 views

Topics:

TreesBinary SearchRecursion

Given the root of a complete binary tree, return the number of the nodes in the tree.

Design an algorithm that runs in less than O(n) time complexity.

Example 1:

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

Example 2:

Input: root = []
Output: 0

Example 3:

Input: root = [1]
Output: 1

Constraints:

The number of nodes in the tree is in the range [0, 5 * 10⁴].
0 <= Node.val <= 5 * 10⁴
The tree is guaranteed to be complete.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can you confirm the tree is a complete binary tree as defined by all levels being completely filled except for possibly the last level, which is filled from left to right?
What is the maximum number of nodes I should expect in the tree? Is there a particular performance target I should aim for?
Can the tree ever be empty (i.e., root is null)? If so, what value should I return?
Is the range of values for each node important? Should I consider integer overflow?
Can you further clarify what you mean by a 'node', is it an integer, or some other complex data structure?

Brute Force Solution

Approach

The goal is to find how many nodes are in the tree. The brute force way to do this is to simply visit every single node and count them.

Here's how the algorithm would work step-by-step:

Start at the very top of the tree, which is called the root.
Go down every possible path in the tree, visiting each node.
For every node you visit, add one to your count.
Keep going until you have checked every single node in the tree.
The final count you have is the total number of nodes in the tree.

Code Implementation

def count_complete_tree_nodes_brute_force(root):
    number_of_nodes = 0

    def traverse_tree(node):
        nonlocal number_of_nodes

        if not node:
            return

        # We are visiting the node, so increment the count.
        number_of_nodes += 1

        traverse_tree(node.left)

        traverse_tree(node.right)

    # Start the traversal from the root
    traverse_tree(root)

    return number_of_nodes

Big(O) Analysis

Time Complexity

O(n) – The provided solution performs a traversal of every node in the tree. The input size, n, is the number of nodes in the tree. The algorithm visits each of these n nodes exactly once. Therefore, the number of operations scales linearly with the number of nodes, resulting in O(n) time complexity.

Space Complexity

O(N) – The provided brute force approach involves visiting every node in the tree. If implemented using recursion, the maximum depth of the recursion call stack will be equivalent to the height of the tree in the worst case (a skewed tree). In the worst-case scenario, the height of the tree is equal to the number of nodes, N. Therefore, the recursion stack could grow to a size of N in the worst case, resulting in O(N) space complexity, where N is the number of nodes in the tree.

Optimal Solution

Approach

The key to efficiently counting nodes in a complete tree is realizing it has a special structure. We don't need to visit every single node; instead, we use the tree's properties to quickly calculate the number of nodes.

Here's how the algorithm would work step-by-step:

First, determine the height of the tree. A complete tree has a guaranteed path down the left side, so efficiently find that depth.
Next, check if the last level of the tree is completely full. To do this, find the height of the right subtree.
If the left and right subtrees have the same height, the left subtree is a perfect binary tree. We know the number of nodes in a perfect tree based on its height.
If the left and right subtrees don't have the same height, the right subtree is one level shorter. Now, the right subtree is a complete binary tree and the left subtree is nearly perfect. We can recursively count the nodes in the right subtree.
We continue this divide-and-conquer approach, leveraging the complete tree's structure to dramatically reduce the work required compared to visiting every node.

Code Implementation

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

class Solution:
    def countNodes(self, root):
        if not root:
            return 0

        def get_height(node):
            height = 0
            while node:
                height += 1
                node = node.left
            return height

        left_height = get_height(root.left)
        right_height = get_height(root.right)

        # If heights are equal, left subtree is perfect.
        if left_height == right_height:

            return (1 << left_height) + self.countNodes(root.right) + 0

        # Otherwise, right subtree is complete but one level shorter.
        else:
            return (1 << right_height) + self.countNodes(root.left) + 0

Big(O) Analysis

Time Complexity

O(log²(n)) – The algorithm relies on recursively exploring subtrees, effectively halving the search space at each level. The height of a complete binary tree with n nodes is log(n). Within each level of the tree (log(n) levels), we perform a constant amount of work to calculate left and right subtree heights. Since calculating subtree heights takes O(log(n)) time in the worst case, and this is done at each of the O(log(n)) levels of the recursion, the overall time complexity is O(log(n) * log(n)), which simplifies to O(log²(n)).

Space Complexity

O(log N) – The space complexity is determined by the recursion depth. The algorithm recursively calls itself on either the left or right subtree. In a complete tree, the height is approximately log N, where N is the number of nodes. Therefore, the maximum depth of the recursion stack is log N, leading to a space complexity of O(log N).

Edge Cases

Case	How to Handle
Null or empty tree	Return 0 immediately if the root is null, representing an empty tree.
Tree with only a root node	Return 1 if only a root node exists, as it represents one node in the tree.
Perfectly balanced complete binary tree	Utilize the formula 2^height - 1 to calculate efficiently without traversing all nodes.
Completely skewed tree (left or right)	Fall back to the O(n) traversal method, as the height calculation shortcut won't apply.
Maximum height tree (based on memory constraints)	Ensure that the recursion depth or iterative stack doesn't exceed memory limits, potentially using an iterative solution.
Integer overflow in height calculation or node count	Use appropriate data types (long) to avoid integer overflow during height calculation or when counting a large number of nodes.
Tree with a very deep left subtree and a shallow right subtree.	Height calculation may still be unbalanced and slow if the tree's right side is significantly shorter than the left.
Tree where the last level is not filled completely from left to right.	The solution should accurately count the number of nodes in the last level by checking each node.

Null or empty tree

How to Handle:

Return 0 immediately if the root is null, representing an empty tree.

Tree with only a root node

How to Handle:

Return 1 if only a root node exists, as it represents one node in the tree.

Perfectly balanced complete binary tree

How to Handle:

Utilize the formula 2^height - 1 to calculate efficiently without traversing all nodes.

Completely skewed tree (left or right)

How to Handle:

Fall back to the O(n) traversal method, as the height calculation shortcut won't apply.

Maximum height tree (based on memory constraints)

How to Handle:

Ensure that the recursion depth or iterative stack doesn't exceed memory limits, potentially using an iterative solution.

Integer overflow in height calculation or node count

How to Handle:

Use appropriate data types (long) to avoid integer overflow during height calculation or when counting a large number of nodes.

Tree with a very deep left subtree and a shallow right subtree.

How to Handle:

Height calculation may still be unbalanced and slow if the tree's right side is significantly shorter than the left.

Tree where the last level is not filled completely from left to right.

How to Handle:

The solution should accurately count the number of nodes in the last level by checking each node.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can you confirm the tree is a complete binary tree as defined by all levels being completely filled except for possibly the last level, which is filled from left to right?
What is the maximum number of nodes I should expect in the tree? Is there a particular performance target I should aim for?
Can the tree ever be empty (i.e., root is null)? If so, what value should I return?
Is the range of values for each node important? Should I consider integer overflow?
Can you further clarify what you mean by a 'node', is it an integer, or some other complex data structure?

Brute Force Solution

Approach

The goal is to find how many nodes are in the tree. The brute force way to do this is to simply visit every single node and count them.

Here's how the algorithm would work step-by-step:

Start at the very top of the tree, which is called the root.
Go down every possible path in the tree, visiting each node.
For every node you visit, add one to your count.
Keep going until you have checked every single node in the tree.
The final count you have is the total number of nodes in the tree.

Code Implementation

def count_complete_tree_nodes_brute_force(root):
    number_of_nodes = 0

    def traverse_tree(node):
        nonlocal number_of_nodes

        if not node:
            return

        # We are visiting the node, so increment the count.
        number_of_nodes += 1

        traverse_tree(node.left)

        traverse_tree(node.right)

    # Start the traversal from the root
    traverse_tree(root)

    return number_of_nodes

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, determine the height of the tree. A complete tree has a guaranteed path down the left side, so efficiently find that depth.
Next, check if the last level of the tree is completely full. To do this, find the height of the right subtree.
If the left and right subtrees have the same height, the left subtree is a perfect binary tree. We know the number of nodes in a perfect tree based on its height.
If the left and right subtrees don't have the same height, the right subtree is one level shorter. Now, the right subtree is a complete binary tree and the left subtree is nearly perfect. We can recursively count the nodes in the right subtree.
We continue this divide-and-conquer approach, leveraging the complete tree's structure to dramatically reduce the work required compared to visiting every node.

Code Implementation

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

class Solution:
    def countNodes(self, root):
        if not root:
            return 0

        def get_height(node):
            height = 0
            while node:
                height += 1
                node = node.left
            return height

        left_height = get_height(root.left)
        right_height = get_height(root.right)

        # If heights are equal, left subtree is perfect.
        if left_height == right_height:

            return (1 << left_height) + self.countNodes(root.right) + 0

        # Otherwise, right subtree is complete but one level shorter.
        else:
            return (1 << right_height) + self.countNodes(root.left) + 0

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty tree	Return 0 immediately if the root is null, representing an empty tree.
Tree with only a root node	Return 1 if only a root node exists, as it represents one node in the tree.
Perfectly balanced complete binary tree	Utilize the formula 2^height - 1 to calculate efficiently without traversing all nodes.
Completely skewed tree (left or right)	Fall back to the O(n) traversal method, as the height calculation shortcut won't apply.
Maximum height tree (based on memory constraints)	Ensure that the recursion depth or iterative stack doesn't exceed memory limits, potentially using an iterative solution.
Integer overflow in height calculation or node count	Use appropriate data types (long) to avoid integer overflow during height calculation or when counting a large number of nodes.
Tree with a very deep left subtree and a shallow right subtree.	Height calculation may still be unbalanced and slow if the tree's right side is significantly shorter than the left.
Tree where the last level is not filled completely from left to right.	The solution should accurately count the number of nodes in the last level by checking each node.

Null or empty tree

How to Handle:

Return 0 immediately if the root is null, representing an empty tree.

Tree with only a root node

How to Handle:

Return 1 if only a root node exists, as it represents one node in the tree.

Perfectly balanced complete binary tree

How to Handle:

Utilize the formula 2^height - 1 to calculate efficiently without traversing all nodes.

Completely skewed tree (left or right)

How to Handle:

Fall back to the O(n) traversal method, as the height calculation shortcut won't apply.

Maximum height tree (based on memory constraints)

How to Handle:

Ensure that the recursion depth or iterative stack doesn't exceed memory limits, potentially using an iterative solution.

Integer overflow in height calculation or node count

How to Handle:

Use appropriate data types (long) to avoid integer overflow during height calculation or when counting a large number of nodes.

Tree with a very deep left subtree and a shallow right subtree.

How to Handle:

Height calculation may still be unbalanced and slow if the tree's right side is significantly shorter than the left.

Tree where the last level is not filled completely from left to right.

How to Handle:

The solution should accurately count the number of nodes in the last level by checking each node.