LeetCode 222: Count Complete Tree Nodes Solution

Master LeetCode problem 222 (Count Complete Tree Nodes), a easy challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

222. Count Complete Tree Nodes

Easy

Binary Search Bit Manipulation Tree Binary Tree

Problem Explanation

Explanation

To solve this problem efficiently, we can use a binary search approach to find the last node in the complete binary tree. Once we find the last node, we can calculate the total number of nodes by counting the nodes in the left and right subtrees recursively. This approach leverages the properties of a complete binary tree to optimize the time complexity to O(log^2(n)).

Find the height of the tree by traversing the left child nodes until we reach a null node.
Perform a binary search on the last level of the tree to find the last node.
Count the nodes in the left and right subtrees recursively.
Calculate the total number of nodes as 2^(height)-1 + nodes in the left and right subtrees.

Time complexity: O(log^2(n)) Space complexity: O(log(n))

Solution Code

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

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 222 (Count Complete Tree Nodes)?

This page provides optimized solutions for LeetCode problem 222 (Count Complete Tree Nodes) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 222 (Count Complete Tree Nodes)?

The time complexity for LeetCode 222 (Count Complete Tree Nodes) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 222 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 222 in Java, C++, or Python.

Back to LeetCode Solutions