Count Complete Tree Nodes

To solve this coding challenge, we need to determine the number of nodes in a complete binary tree with a complexity that performs better than O(n). The key observation here is that because the tree is complete, we can use its properties to achieve a time complexity of O(log^2(n)).

Explanation

  1. Understanding Complete Binary Trees :
    • A complete binary tree is a binary tree where every level is fully filled, except possibly the last level.
    • Nodes in the last level are filled from left to right.
  2. Optimizing the Algorithm :
    • We need to utilize the properties of complete binary trees to count the nodes efficiently.
    • Instead of traversing each node (which leads to O(n) complexity), we can perform recursive binary search to count the nodes.
  3. Key Steps :
    • Calculate the depth of the tree.
    • Use a recursive approach to count the nodes by comparing the left and right subtrees.
    • If the left and right subtree heights are equal, then the left subtree is a complete tree.
  4. Base Case and Recursion :
    • If the tree is empty, return 0.
    • If the left and right subtree heights are equal, the left subtree is a complete tree.
    • If not, then the right subtree is a complete tree.
  5. Time Complexity :
    • Each recursive call checks the depths, leading to O(log n) iterations, and each depth calculation is O(log n).
    • Hence, we achieve a time complexity of O(log^2(n)).
    Detailed Steps in Pseudocode:
  6. Calculate Tree Depth :
    • Create a helper function that calculates the depth of the leftmost path.
  7. Count Nodes Using Depth :
    • Utilize a recursive approach to compare the depths of the left and right subtrees.
    • If the left depth equals the right depth, the left subtree is complete.
    • Adjust the recursion to count nodes in the right subtree if the left depth does not equal the right depth.
                                                
// Helper function to compute the depth of the tree
function computeDepth(node):
if node is None:
return 0
depth = 0
while node is not None:
node = node.left
depth += 1
return depth

// Main function to count nodes in a complete binary tree
function countCompleteTreeNodes(root):
if root is None: 
// Base case: if the tree is empty
return 0

leftDepth = computeDepth(root.left)
rightDepth = computeDepth(root.right)

if leftDepth == rightDepth: 
// If left subtree is complete
// Left subtree has 2^leftDepth - 1 nodes + 1 (the root)
// Recur on right subtree
return 2^leftDepth + countCompleteTreeNodes(root.right)
else: 
// If right subtree is complete but one level smaller
// Right subtree has 2^rightDepth - 1 nodes + 1 (the root)
// Recur on left subtree
return 2^rightDepth + countCompleteTreeNodes(root.left)
    Step-by-Step Explanation of Pseudocode
  8. Compute Depth :
    • The
      computeDepth
      function computes the depth of a subtree starting from its root by following the left children. This gives the depth of the leftmost path.
  9. Count Nodes :
    • The
      countCompleteTreeNodes
      function first checks if the tree is empty.
    • It then computes the depths of both left and right subtrees originating from the root.
    • If depths are equal, this means the left subtree is a perfect binary tree. Thus, the subtree has \(2^{\text{leftDepth}}\) nodes. Then, we recurse into the right subtree.
    • If depths are not equal, the right subtree is a perfect binary tree of height one less than the left subtree. We thus recurse into the left subtree.
This approach efficiently utilizes the properties of complete binary trees to arrive at the total node count in a significantly optimized manner.