deepSWE.io

Count Complete Tree Nodes

TreesBinary Search

Problem Statement

Given the `root` of a **complete binary tree**, return the number of the nodes in the tree.

Example

Output: 6

Algorithm Explanation

A naive solution would be to traverse the entire tree and count the nodes. However, we can do better by taking advantage of the "complete" property of the tree.

Algorithm Steps

Calculate Height: We can find the height of the tree by only traversing the left side.
Binary Search on Last Level: The number of nodes in a complete tree is between `2^h` and `2^(h+1) - 1`. We can binary search for the last existing node in the last level to find the exact count.
Check Existence: To check if a node at a certain index in the last level exists, we can traverse from the root. At each step, we compare the index with the midpoint of the current range and decide whether to go left or right.

Start

Starting count.

Left Depth: 0

Right Depth: 0

Count: 0

Count Complete Tree Nodes Solution


class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        
        left_depth = self.get_depth(root.left)
        right_depth = self.get_depth(root.right)
        
        if left_depth == right_depth:
            return (1 << left_depth) + self.countNodes(root.right)
        else:
            return (1 << right_depth) + self.countNodes(root.left)

    def get_depth(self, node):
        depth = 0
        while node:
            depth += 1
            node = node.left
        return depth