712545. Count Number of Nodes in a Binary Tree
Count Number of Nodes in a Binary Tree
Slug: count-number-of-nodes-in-a-binary-tree Difficulty: Medium Id: 712545 Topic Tags: None Company Tags: None
Summary
Counting the number of nodes in a binary tree is a fundamental problem that involves traversing the tree and keeping track of the node count. This problem requires understanding basic concepts of binary trees, such as traversal methods.
Detailed Explanation
The approach to solve this problem involves using a simple tree traversal algorithm. We will use an in-order traversal (left-root-right) to visit each node in the tree. During the traversal, we keep track of the current node and increment the count for each node visited. This ensures that all nodes are counted accurately.
Here's a step-by-step breakdown of the solution:
- Start at the root node.
- Traverse the left subtree (if it exists).
- Visit the current node and increment the node count.
- Traverse the right subtree (if it exists).
- Repeat steps 2-4 until all nodes have been visited.
The time complexity for this algorithm is O(n), where n is the number of nodes in the tree, since we visit each node exactly once. The space complexity is O(h), where h is the height of the tree, as we need to store the current node and its subtrees during the traversal.
Optimized Solutions
Java
public int countNodes(Node root) {
if (root == null) return 0;
int count = 1; // include the root node in the count
count += countNodes(root.left);
count += countNodes(root.right);
return count;
}