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.

Continue Reading →