222. Count Complete Tree Nodes

EasyBit ManipulationTreeBinary SearchBinary Tree

Problem Description

The problem provides a complete binary tree and requires us to determine the total number of nodes in the tree. A complete binary tree is a tree where all levels are fully filled except possibly the last level, which is filled from left to right. Such a tree has a special property where the number of nodes at the last level is between 1 and (2^h), where (h) is the height of the last level.

Our task is to find a method to count the nodes of such a binary tree in less than (O(n)) time complexity, where (n) is the number of nodes in the tree.

Intuition

The intuition behind the solution is to leverage the properties of the complete binary tree, which allow us to use a divide and conquer strategy much more efficiently than checking each node. Because in a complete binary tree, either the left or the right subtree is a perfect binary tree, we can use this property to reduce the problem size at each step.

By calculating the depth (height) of the leftmost and rightmost paths separately, we can determine if the last level is completely filled or not.

If the left and right depths are the same, it means that the left subtree is a perfect binary tree with (2^{\text{depth}} - 1) nodes, and we only need to count the nodes in the right subtree recursively.
If the left and right depths are not the same, it means the last level of the tree is not full, and the right subtree is a perfect binary tree with (2^{\text{right depth}} - 1) nodes, and we count the nodes in the left subtree recursively.

By doing this recursive action, we exponentially decrease the number of nodes we have to visit, thus reducing the time complexity to less than (O(n)).

Learn more about Tree, Binary Search and Binary Tree patterns.

Solution Approach

The solution uses a recursive approach to solve the problem efficiently. The key is to identify whether the left or right subtree forms a perfect binary tree. To make this identification, we perform the following steps in the given Python code:

Define an inner function named depth that calculates the depth of a binary tree by traversing leftward until there are no more nodes. It incrementally increases a counter d on each iteration, which is returned as the tree's depth from the root to the deepest left leaf node.
Check if the given root node is None and return 0 because an empty tree has no nodes.
Calculate the depths of the left and right subtrees of the root using the depth function.
If the left and right depths are equal (left == right), according to the properties of complete binary trees, the left subtree is perfect and contains 2^left - 1 nodes. We then add 1 (the root node) to this number and recursively count the nodes in the right subtree.
If the left and right depths are not equal, the last level is not fully filled, so the perfect subtree is the right subtree with 2^right - 1 nodes. We again add 1 for the root node and recursively count the nodes in the left subtree.

In both cases, the expression (1 << left) or (1 << right) is used to calculate (2^\text{left}) or (2^\text{right}) respectively. This bit-shift operation is a fast way to compute powers of two.

By calling this recursive solution on appropriate subtrees and keeping track of the number of nodes, the function can calculate the total number of nodes in a complete binary tree efficiently with the time complexity better than (O(n)).

Overall, the implementation utilizes the divide and conquer principle by breaking down the problem into smaller subproblems. It also takes advantage of the characteristics of complete binary trees and utilizes recursion with depth calculation to minimize the nodes visited during the counting process.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach:

Suppose we have the following complete binary tree:

We want to find the total number of nodes in this tree efficiently.

First, we calculate the depth of the leftmost path. Starting from the root node (1) and moving left, we reach node (4) without any further left child nodes. Thus, the leftmost depth is 3.
Then, we calculate the depth of the rightmost path. Again, starting from the root node (1) and this time moving right, we reach node (3) which does not have a right child. Hence, the rightmost depth is also 3.
Since the leftmost depth (3) is equal to the rightmost depth (3), we conclude that the left subtree is a perfect binary tree and therefore has (2^{\text{depth}} - 1) nodes, which in this case is (2^3 - 1 = 7) nodes. However, because we only have 5 nodes in the left subtree (nodes 1, 2, 4, and 5), it shows that the tree is not full and the last level is not completely populated.
Now, since we established the leftmost and rightmost depths are same, we know that the left subtree is perfect (except for the last level). We count the nodes in this perfect subtree portion, which is (2^2 - 1) because the actual last level is not full, so we take one less depth, giving us (2^2 - 1 = 3) nodes (1, 2, and 5).
Next, we add 1 for the root node to the number we just counted, which gives us 4, representing the left subtree including the root.
Finally, we move on to the right subtree and recursively apply the same process. The right subtree has a depth of 2, so following the same logic, it has (2^2 - 1 = 3) nodes (nodes 3 and 6, plus the imaginary node at the depth 2 position).
By combining the counts of both subtrees and the root, we get (3 + 1 + 3 = 7). However, remember that the right subtree was not perfect and had only 2 nodes (3 and 6), we correct the count to (4 + 2 = 6).

Hence, the tree in our example has a total of 6 nodes. This method, as explained in the solution approach, is more efficient than traversing every node in the tree because it utilizes the properties of a complete binary tree to determine the count of nodes efficiently.

Solution Implementation

1class TreeNode:
2    # Initializing the TreeNode structure as described
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8class Solution:
9    def countNodes(self, root: Optional[TreeNode]) -> int:
10        # Helper function to calculate the depth of the tree
11        def calculate_depth(node):
12            depth = 0
13            while node:
14                depth += 1
15                # Move to the next left node to calculate full depth
16                node = node.left
17            return depth
18
19        # Main function starts here
20        # If the root is None, the tree is empty and has no nodes
21        if root is None:
22            return 0
23
24        # Calculate the depth of the left and right subtrees
25        left_depth = calculate_depth(root.left)
26        right_depth = calculate_depth(root.right)
27
28        # If the left and right subtrees have the same depth, it means the left subtree is complete
29        # We can directly calculate the nodes in the left subtree using the formula (2^depth) - 1
30        # and then recursively count the nodes in the right subtree.
31        if left_depth == right_depth:
32            # Left shift operation (1 << left_depth) calculates 2^left_depth
33            # Add the count of nodes in the right subtree.
34            return (1 << left_depth) + self.countNodes(root.right)
35      
36        # If the left and right subtree depths differ, the right subtree is complete
37        # We calculate the nodes for the right subtree using the formula (2^depth) - 1
38        # and recursively count the nodes in the left subtree.
39        else:
40            # Add the count of nodes in the left subtree.
41            return (1 << right_depth) + self.countNodes(root.left)
42
43# The TreeNode and Solution classes usage example (the actual nodes should be instantiated with their respective values)
44# root = TreeNode(1)
45# root.left = TreeNode(2)
46# root.right = TreeNode(3)
47# root.left.left = TreeNode(4)
48# root.left.right = TreeNode(5)
49# root.right.left = TreeNode(6)
50# solution = Solution()
51# number_of_nodes = solution.countNodes(root)
52

1// Custom definition for a binary tree node.
2class TreeNode {
3    int val; // holds the value of the node
4    TreeNode left; // reference to the left child
5    TreeNode right; // reference to the right child
6  
7    // Constructor to initialize the node with no children
8    TreeNode() {}
9  
10    // Constructor to initialize the node with a specific value
11    TreeNode(int val) { this.val = val; }
12  
13    // Constructor to initialize the node with a value and references to left and right children
14    TreeNode(int val, TreeNode left, TreeNode right) {
15        this.val = val;
16        this.left = left;
17        this.right = right;
18    }
19}
20
21// Class containing a solution method to count the nodes of a binary tree.
22class Solution {
23  
24    // Method that returns the count of nodes in a complete binary tree.
25    public int countNodes(TreeNode root) {
26        // Base case: if the tree is empty, return 0
27        if (root == null) {
28            return 0;
29        }
30
31        // Compute the depth of the left subtree
32        int leftDepth = computeDepth(root.left);
33        // Compute the depth of the right subtree
34        int rightDepth = computeDepth(root.right);
35
36        // Check if the left and right depths are equal
37        if (leftDepth == rightDepth) {
38            // If equal, the left subtree is complete and we add its node count to the recursive count of the right subtree
39            return (1 << leftDepth) + countNodes(root.right);
40        } else {
41            // If not equal, the right subtree is complete and we add its node count to the recursive count of the left subtree
42            return (1 << rightDepth) + countNodes(root.left);
43        }
44    }
45
46    // Helper method that computes the depth of the tree (distance from the root to the deepest leaf node)
47    private int computeDepth(TreeNode root) {
48        int depth = 0;
49        // Loop to travel down the left edge of the tree until a null is encountered
50        for (; root != null; root = root.left) {
51            depth++;
52        }
53        // Return the depth of the tree
54        return depth;
55    }
56}
57

1/**
2 * Definition for a binary tree node.
3 */
4struct TreeNode {
5    int val;
6    TreeNode *left;
7    TreeNode *right;
8    TreeNode() : val(0), left(nullptr), right(nullptr) {}
9    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
10    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
11};
12
13class Solution {
14public:
15    /**
16     * Counts the number of nodes in a complete binary tree.
17     *
18     * @param root The root node of the binary tree.
19     * @return The total number of nodes in the tree.
20     */
21    int countNodes(TreeNode* root) {
22        if (!root) {
23            // If the tree is empty, return a count of 0.
24            return 0;
25        }
26      
27        // Calculate the depth of the left and right subtrees.
28        int leftDepth = calculateDepth(root->left);
29        int rightDepth = calculateDepth(root->right);
30      
31        // If the depths are equal, it means the left subtree is complete and we can use the formula to calculate the number of nodes in a complete subtree, which is 2^height - 1, and add the number of nodes in the right subtree.
32        if (leftDepth == rightDepth) {
33            return (1 << leftDepth) + countNodes(root->right);
34        }
35      
36        // If the depths are not equal, the right subtree must be complete, and we calculate the number of nodes in the left subtree. We then add the nodes in the right subtree (2^height - 1).
37        return (1 << rightDepth) + countNodes(root->left);
38    }
39
40    /**
41     * Calculates the depth of the tree (distance to the leaf) following the left child.
42     *
43     * @param node The node to measure the depth from.
44     * @return The depth of the subtree.
45     */
46    int calculateDepth(TreeNode* node) {
47        int depth = 0;
48        while (node) {
49            // Move to the left child and increment the depth count.
50            node = node->left;
51            ++depth;
52        }
53        return depth;
54    }
55};
56

1// Definition for a binary tree node in TypeScript using an interface.
2interface TreeNode {
3  val: number;
4  left: TreeNode | null;
5  right: TreeNode | null;
6}
7
8// Function to create a new TreeNode instance with default values if not provided.
9function createTreeNode(
10  value: number = 0,
11  leftNode: TreeNode | null = null,
12  rightNode: TreeNode | null = null
13): TreeNode {
14  return { val: value, left: leftNode, right: rightNode };
15}
16
17/**
18 * Recursively counts the number of nodes in a complete binary tree.
19 * @param root The root of the binary tree.
20 * @return The total number of nodes in the binary tree.
21 */
22const countNodes = (root: TreeNode | null): number => {
23  // Helper function to find the depth of the tree.
24  const getDepth = (node: TreeNode | null): number => {
25    let depth = 0;
26    while (node !== null) {
27      depth++;
28      node = node.left; // Go to leftmost node to find the depth.
29    }
30    return depth;
31  };
32
33  // Base case: if the tree is empty, return 0.
34  if (root === null) {
35    return 0;
36  }
37
38  // Calculate the depth of the left and right subtrees.
39  const leftDepth = getDepth(root.left);
40  const rightDepth = getDepth(root.right);
41
42  // Check if the left and right subtrees have the same depth.
43  if (leftDepth === rightDepth) {
44    // If depths are equal, left subtree is a perfect binary tree.
45    // Calculate the number of nodes in the left subtree as 2^leftDepth - 1
46    // Count the nodes in the right subtree recursively.
47    return (1 << leftDepth) + countNodes(root.right);
48  } else {
49    // If depths are not equal, right subtree is a perfect binary tree.
50    // Calculate the number of nodes in the right subtree as 2^rightDepth - 1
51    // Count the nodes in the left subtree recursively.
52    return (1 << rightDepth) + countNodes(root.left);
53  }
54};
55

Time and Space Complexity

The given Python code is designed to count the number of nodes in a complete binary tree. A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

Time Complexity

The time complexity of the algorithm depends on the structure of the tree. Each recursive call to countNodes either moves to the right or to the left subtree and computes the height of the opposite subtree. The depth function takes time proportional to the height of the tree, which is O(log n) for a complete binary tree (where n is the number of nodes).

The recurrence relation for the worst-case time complexity can be approximated as T(n) = T(n/2) + O(log n) because at each step one of the subtrees is approximately half the size of the original tree and we spend O(log n) time to calculate the depth.

Solving this recurrence gives us a time complexity of O(log^2 n). This is because for each level of recursion, which is logarithmic in the number of nodes, we compute the depth of a subtree, which is also logarithmic in the number of nodes.

Space Complexity

The space complexity of the code is primarily determined by the maximum size of the call stack since the function is recursive. In the worst case, the recursion goes O(log n) levels deep because the function will be called recursively on subtrees of decreasing size until the size becomes 1.

Therefore, the space complexity is O(log n), due to the call stack of the recursive function calls.

These complexities are true assuming that the underlying Python implementation handles tail recursion properly.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which technique can we use to find the middle of a linked list?

Fast-slow pointers

Two pointers moving in opposite direction

Binary search

Depth first search

I don't know