Count Complete Tree Nodes
Given a complete binary tree, count the number of nodes.
Constraints:
- The tree is a complete binary tree.
- The number of nodes in the tree is in the range [1, 10^4].
- The values of the nodes are in the range [1, 10^4].
Examples:
Input: [1,2,3,4,5,6]
Output: 6
Explanation: The tree is a complete binary tree with 6 nodes.
Solutions
Level Order Traversal
Time: O(n)Space: O(n)
This solution uses a level order traversal to count the number of nodes in the tree. It starts by checking if the root is null, and if so, returns 0. Then it initializes a queue with the root node and a count variable to 0. It enters a loop that continues until the queue is empty. In each iteration, it dequeues a node, increments the count, and enqueues the node's left and right children if they exist. Finally, it returns the count.
function countNodes(root) {
if (!root) return 0;
let queue = [root];
let count = 0;
while (queue.length) {
let node = queue.shift();
count++;
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
return count;
}
Follow-up:
How would you modify the solution to count the number of nodes in a binary tree that is not complete?
