Binary Search     Binary Tree     C++     Depth-First Search     Medium     Recursion     Tree    

Problem Statement:

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.

 

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 * 104].
  • 0 <= Node.val <= 5 * 104
  • The tree is guaranteed to be complete.

Solution:

First, let us define the concept of a “full” tree: a tree with no null nodes in the last level ie full upto its complete height. (Consider height of root as 0, level 1 as 1 etc) IMP: What is the #(Nodes) in a full tree of height h Ans: 2^(h+1) - 1

Now, given that we have “complete” tree of height h, we can say that either the left subtree is a “full” tree of height h-1 or the right subtree is a “full” tree of height h-2.

In the first case we have

 
countNodes(root) = 2^h + countNodes(root->right)

(2^h = 2^h - 1 for left subtree and 1 for root) and in the second case, we have

 
countNodes(root) = 2^(h-1) + countNodes(root->left)

(2^(h-1) = 2^(h-1) - 1 for right subtree and 1 for root)

C++ code:

 
class Solution {
public:
    int height(TreeNode *root)
    {
        return root == NULL ? -1 : 1+height(root->left);
    }
    int countNodes(TreeNode* root) 
    {
        if (!root) return 0;
        int h = height(root);
        if (h==0) return 1;
        if (height(root->right)==h-1)
            return (1<<h) + countNodes(root->right);
        else
            return (1<<h-1) + countNodes(root->left);
        return -1;
    }
};
 
 
TC=O((log n)^2)