Solution For Count Complete Tree Nodes

Problem Statement:
Given the root of a complete binary tree, return the number of the nodes in the 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.

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

Input: root = [] Output: 0

Approach:
Since given is a complete binary tree, it is ensured all nodes except the last level are populated completely. We can find the count of nodes from the leftmost path and rightmost path of the tree. We can compare the depth of the leftmost and rightmost node. If both nodes are at the same depth, then the number of nodes in the tree can be calculated as 2^height – 1 else we can recursively apply the same approach to the left and right subtrees.

Algorithm:
1. If root is null, return 0
2. We will check the depth of the leftmost and rightmost nodes by traversing the tree.
3. If both nodes are at the same depth, the number of nodes can be calculated as 2^height – 1
4. Else, recursively apply the same approach to the left and right subtrees.
5. Return the sum of all the nodes calculated.

Code:

“`
class Solution {
public:
int countNodes(TreeNode* root) {
if(root==NULL)
return 0;

    int leftHeight = findLeftHeight(root);
    int rightHeight = findRightHeight(root);

    if(leftHeight == rightHeight)
        return pow(2,leftHeight)-1;

    return 1+countNodes(root->left)+countNodes(root->right);
}

int findLeftHeight(TreeNode* root)
{
    if(root==NULL)
        return 0;
    int height = 0;
    while(root!=NULL)
    {
        height++;
        root=root->left;
    }
    return height; 
}

int findRightHeight(TreeNode* root)
{
    if(root==NULL)
        return 0;
    int height = 0;
    while(root!=NULL)
    {
        height++;
        root=root->right;
    }
    return height; 
}

};
“`

Step by Step Implementation For Count Complete Tree Nodes

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int countNodes(TreeNode root) {
        // if the tree is empty, return 0
        if (root == null) {
            return 0;
        }
        
        // if the tree is not empty, then recursively count the number of nodes in the left and right subtrees
        int left = countNodes(root.left);
        int right = countNodes(root.right);
        
        // the total number of nodes is the sum of the nodes in the left and right subtrees, plus the root node
        return left + right + 1;
    }
}

# Definition for a binary tree node.
# 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: TreeNode) -> int:
        # if the tree is empty, return 0
        if not root:
            return 0
        
        # if the tree is not empty, get the height of the left and right subtrees
        left_height = self.getHeight(root.left)
        right_height = self.getHeight(root.right)
        
        # if the left and right subtree heights are the same,
        # then the tree is a perfect binary tree and we can
        # simply return 2^h - 1, where h is the height of the tree
        if left_height == right_height:
            return 2**left_height - 1
        
        # if the left and right subtree heights are not the same,
        # then the tree is not a perfect binary tree and we must
        # recursively call countNodes on the left and right subtrees
        else:
            return 1 + self.countNodes(root.left) + self.countNodes(root.right)
        
    def getHeight(self, root):
        # if the tree is empty, the height is 0
        if not root:
            return 0
        
        # if the tree is not empty, return 1 + the maximum height
        # of the left and right subtrees
        return 1 + max(self.getHeight(root.left), self.getHeight(root.right))

var countNodes = function(root) {
    
    // if the tree is empty, return 0
    if (!root) return 0;
    
    // initialize count to 1 for the root node
    let count = 1;
    
    // recursively call countNodes on the left and right subtrees
    count += countNodes(root.left);
    count += countNodes(root.right);
    
    // return the total count
    return count;
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int countNodes(TreeNode* root) {
        if(!root)
            return 0;
        int lh = 0, rh = 0;
        TreeNode *l = root, *r = root;
        while(l){
            lh++;
            l = l->left;
        }
        while(r){
            rh++;
            r = r->right;
        }
        if(lh == rh)
            return pow(2,lh)-1;
        return countNodes(root->left) + countNodes(root->right) + 1;
    }
};

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int CountNodes(TreeNode root) {
        //if the tree is empty, return 0
        if(root == null){
            return 0;
        }
        //if the tree is not empty, then recursively call the CountNodes method on the left and right subtrees
        return 1 + CountNodes(root.left) + CountNodes(root.right);
    }
}