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.
from collections import deque
def countNodes(root):
if not root:
return 0
queue = deque([root])
count = 0
while queue:
node = queue.popleft()
count += 1
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return countFollow-up:
How would you modify the solution to count the number of nodes in a binary tree that is not complete?
