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.
Examples:
Example 1:
Input: root = [1,2,3,4,5,6]
Output: 6
Example 2:
Input: root = []
Output: 0
Example 3:
Input: root = [1]
Output: 1Solution in Python
Approach
- Tree Height:
- The height of a complete binary tree can be easily determined by following the leftmost path from the root. This gives the total number of levels.
- Binary Search on the Last Level:
- The total number of nodes can be determined based on the height of the tree. However, the last level might not be completely full, so we use binary search to determine how many nodes are present in the last level.
- Each level before the last is fully filled, so the number of nodes for all levels except the last can be directly calculated.
- For the last level, we can perform a binary search to determine how many nodes are present.
- Time Complexity:
- Since the tree is complete, the height is at most
log(n). Binary search on the last level also takeslog(n)steps, leading to an overall complexity of O(log(n)2).
- Since the tree is complete, the height is at most
Python
class Solution:
def countNodes(self, root: Optional[TreeNode]) -> int:
# Helper function to calculate the depth of the tree (i.e., height)
def get_depth(node):
depth = 0
while node:
node = node.left
depth += 1
return depth
# If the tree is empty, return 0
if not root:
return 0
# Calculate the depth of the left and right subtrees
left_depth = get_depth(root.left)
right_depth = get_depth(root.right)
# If the left and right subtree depths are the same, the left subtree is a perfect binary tree
# Therefore, we can add the nodes from the left subtree (which is 2^left_depth - 1) plus the root,
# and then recurse on the right subtree.
if left_depth == right_depth:
return (1 << left_depth) + self.countNodes(root.right)
else:
# If the left and right depths are different, the right subtree is a perfect binary tree
# with height one less than the left subtree. We can count all nodes in the right subtree
# and recurse on the left subtree.
return (1 << right_depth) + self.countNodes(root.left)Detailed Explanation
get_depthhelper function:- This function calculates the depth (height) of the tree by following the leftmost path. It keeps moving left from the root node until it reaches
Noneand counts how many steps it took. This gives the depth of the tree.
- This function calculates the depth (height) of the tree by following the leftmost path. It keeps moving left from the root node until it reaches
- Recursive counting logic:
- We calculate the depth of the left subtree (
left_depth) and the right subtree (right_depth). - If the depths are the same, it means the left subtree is a perfect binary tree (fully filled), so we can calculate the number of nodes in the left subtree as
2^left_depth - 1, then add 1 for the root node and recurse on the right subtree. - If the depths are different, the right subtree is a perfect binary tree, and we calculate its number of nodes as
2^right_depth - 1, then add 1 for the root node and recurse on the left subtree.
- We calculate the depth of the left subtree (
- Base Case:
- If the tree is empty (
root is None), we return 0 because there are no nodes.
- If the tree is empty (
Time Complexity
- Time complexity: O(log(n)2). Calculating the depth takes O(log(n)), and we perform this calculation recursively while recursing into either the left or right subtree, resulting in an overall time complexity of O(log(n) * log(n)).
- Space complexity: O(log(n)) due to the recursion stack depth in a balanced binary tree.
This approach efficiently counts the nodes in a complete binary tree in less than O(n) time.
Solution in Javascript
JavaScript
/**
* @param {TreeNode} root
* @return {number}
*/
var countNodes = function(root) {
// Helper function to calculate the depth of the tree
const getDepth = (node) => {
let depth = 0;
while (node) {
node = node.left;
depth++;
}
return depth;
};
// If the tree is empty, return 0
if (!root) return 0;
// Calculate the depth of the left and right subtrees
let leftDepth = getDepth(root.left);
let rightDepth = getDepth(root.right);
// If the left and right depths are the same, it means the left subtree is a perfect binary tree
// Therefore, the number of nodes in the left subtree is 2^leftDepth - 1, plus the root node,
// and we need to recursively count nodes in the right subtree.
if (leftDepth === rightDepth) {
return (1 << leftDepth) + countNodes(root.right);
} else {
// If the depths are different, it means the right subtree is a perfect binary tree
// with height rightDepth, so we can count all nodes in the right subtree,
// plus the root node, and then recursively count nodes in the left subtree.
return (1 << rightDepth) + countNodes(root.left);
}
};Solution in Java
Java
class Solution {
// Helper function to calculate the depth of the tree by going down the leftmost path
private int getDepth(TreeNode node) {
int depth = 0;
while (node != null) {
node = node.left;
depth++;
}
return depth;
}
public int countNodes(TreeNode root) {
// If the tree is empty, return 0
if (root == null) return 0;
// Calculate the depth of the left and right subtrees
int leftDepth = getDepth(root.left);
int rightDepth = getDepth(root.right);
// If the depths are the same, it means the left subtree is a perfect binary tree
if (leftDepth == rightDepth) {
// The number of nodes in the left subtree is 2^leftDepth - 1 (plus the root node)
// We then recurse on the right subtree to count its nodes
return (1 << leftDepth) + countNodes(root.right);
} else {
// If the depths are different, it means the right subtree is a perfect binary tree
// The number of nodes in the right subtree is 2^rightDepth - 1 (plus the root node)
// We then recurse on the left subtree to count its nodes
return (1 << rightDepth) + countNodes(root.left);
}
}
}Solution in C#
C#
public class Solution {
// Helper function to calculate the depth by going down the leftmost path
private int GetDepth(TreeNode node) {
int depth = 0;
while (node != null) {
node = node.left;
depth++;
}
return depth;
}
public int CountNodes(TreeNode root) {
// Base case: if the tree is empty, return 0
if (root == null) return 0;
// Calculate the depth of the left and right subtrees
int leftDepth = GetDepth(root.left);
int rightDepth = GetDepth(root.right);
// If the left and right depths are the same, the left subtree is a perfect binary tree
if (leftDepth == rightDepth) {
// The number of nodes in the left subtree is 2^leftDepth - 1, plus the root node
// We then recurse on the right subtree
return (1 << leftDepth) + CountNodes(root.right);
} else {
// If depths are different, the right subtree is a perfect binary tree
// The number of nodes in the right subtree is 2^rightDepth - 1, plus the root node
// We then recurse on the left subtree
return (1 << rightDepth) + CountNodes(root.left);
}
}
}