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.
public int countNodes(TreeNode root) {
if (root == null) return 0;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
int count = 0;
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
count++;
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(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?
