Count Complete Tree Nodes

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 2h nodes inclusive at the last level h. Design an algorithm that runs in less than O(n) time complexity.

Approach 1:

class Solution {
    public int countNodes(TreeNode root) {
        return root != null ? 1 + countNodes(root.right) + countNodes(root.left) : 0;
    }
}
                

Time Complexity: O(n) and Space Complexity: O(n)

The problem Count Complete Tree Nodes requires counting the number of nodes in a complete binary tree. A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

Problem Statement

Given the root of a complete binary tree, you need to return the total number of nodes in the tree.

Approach to Solve the Problem

A complete binary tree is defined as a binary tree where all levels except possibly the last are completely filled. The nodes in the last level are as left as possible. To count the nodes in such a tree efficiently, we can take advantage of its special properties.

A naive approach would be to perform a depth-first search (DFS) or breadth-first search (BFS) traversal to count all nodes, but that would be inefficient. A better approach uses the structure of the complete binary tree to reduce the time complexity.

Optimal Approach:

The most efficient way to solve this problem is to use the fact that a complete binary tree is almost like a perfect binary tree except possibly at the last level. To count the nodes, we can perform a binary search-like approach to calculate the height of the tree and count nodes more effectively.

• First, calculate the height of the leftmost path from the root to the bottom (this will give us the height of the tree).
• Then, recursively check the number of nodes at each level by performing a binary search-like traversal from the root to the last level.
• If the tree is a perfect binary tree, we can directly calculate the number of nodes as 2^height - 1. Otherwise, count nodes recursively in the left and right subtrees and combine them.

Implementation

Here is the Python 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 treeHeight(node):
            height = 0
            while node:
                height += 1
                node = node.left
            return height
        
        def countNodesRecursive(node, height):
            if not node:
                return 0
            left_height = treeHeight(node.left)
            right_height = treeHeight(node.right)
            
            if left_height == right_height:
                return (1 << left_height) + countNodesRecursive(node.right, height - 1)
            else:
                return (1 << right_height) + countNodesRecursive(node.left, height - 1)
        
        height = treeHeight(root)
        return countNodesRecursive(root, height)
        

Here is the Java implementation:

public class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        int height = getHeight(root);
        
        if (height == 0) {
            return 0;
        }
        
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        
        if (leftHeight == rightHeight) {
            return (1 << leftHeight) + countNodes(root.right);
        } else {
            return (1 << rightHeight) + countNodes(root.left);
        }
    }
    
    private int getHeight(TreeNode node) {
        int height = 0;
        while (node != null) {
            height++;
            node = node.left;
        }
        return height;
    }
}
        

Example

Consider the following complete binary tree:

            Tree Structure:
                1
               / \
              2   3
             / \   /
            4   5 6
        

In this tree, the number of nodes is 6. The complete tree property is maintained, with all levels filled except the last one, which is as left as possible.

Another example:

            Tree Structure:
                1
               / \
              2   3
             / \
            4   5
        

In this case, the number of nodes is 5. The tree is complete, with all levels filled except the last one, which has two nodes positioned leftmost.

Complexity Analysis

Time Complexity: O(log² n), where n is the number of nodes in the binary tree. The height of the tree is logarithmic in the number of nodes, and at each level, we perform a constant-time operation to count the nodes.

Space Complexity: O(log n), due to the recursive calls, as we are using the height of the tree as a parameter in the recursive function.

Applications

• Helpful in determining the number of nodes in a complete binary tree where direct counting would be inefficient.
• Efficient in solving problems related to binary heaps and trees used in priority queues.
• Can be applied in scenarios requiring balanced binary trees for optimal search and access times.

Conclusion

The Count Complete Tree Nodes problem leverages the structure of a complete binary tree to count nodes efficiently. By using the height of the tree and performing a recursive traversal, we can calculate the number of nodes without needing to traverse every single node. This method significantly reduces the time complexity when compared to a straightforward depth-first or breadth-first search approach.

This problem is an excellent example of using tree properties to optimize operations, which is a valuable skill in algorithm design and problem-solving.