222. Count Complete Tree Nodes

Count Complete Tree Nodes

Problem Description

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.

Approach) Recursion

Assuming that the tree has n layers, first, calculate the number of nodes of the n−1 layer full binary tree.

then calculate the number of nodes in the last layer.

Get the nth layer's MidNode by root->left->right->right....

The subtree based on the complete binary tree is also a complete binary tree, which has:

• If MidNode is null, recursively calculates the number of nodes in the last layer of root->left;
• If MidNode is not null, it means that the left subtree is a full tree. Recursively calculate the number of nodes in the last layer of the root->right subtree,then plus the number of left full tree nodes.

var countNodes = function(root) {
	if(!root) return 0;
	if(root.left === null) return 1;
	let height = 0;
	let nodesum = 0;
	let curNode = root;
	while(curNode.left){
		nodesum += (1 << height);
		height++;
		curNode = curNode.left;
	}
	let totalNode = nodesum + countLastLevel(root, height);
	return totalNode;
};

function countLastLevel(root, height){
	if(height === 1){
		if(root.right !== null){
			return 2;
		}else if(root.left !== null){
			return 1;
		}else {
			return 0;
		}
	}
	let midNode = root.left;
	let curHeight = 1;
	while(curHeight < height) {
		curHeight++;
		midNode = midNode.right;
	}
	if(midNode === null){
		return countLastLevel(root.left, height-1);
	}
	else{
		return (1<<(height-1)) + countLastLevel(root.right, height-1);
	}
}

Approach) DFS (Depth-First Search)

/**
 * @param {TreeNode} root
 * @return {number}
 */
var countNodes = function(root) {
    let count = 0;
    root && traverse(root);
    return count;
    
    function traverse(node) {
        count += 1;
        node.left && traverse(node.left);
        node.right && traverse(node.right);
    };
};

Approach) Stack

var countNodes = function(root) {
    if(!root) return 0;
    var stack = [root];
    var count = 0;
    while(stack.length){
        var node = stack.pop();
        count++;
        if(node.left) stack.push(node.left);
        if(node.right) stack.push(node.right);
    }
    return count;
};

Approach) Short Recursion 

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var countNodes = function(root) {
    if (!root) return 0;
 
    return countNodes(root.left) + countNodes(root.right) + 1;
};

Conclusion

That’s all folks! In this post, we solved LeetCode problem 222. Count Complete Tree Nodes

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!