Count Complete Tree Nodes

class Solution {
    // Calculate depth of tree
    public int findDepth(TreeNode node) {
        int depth = 0;
        while (node.left != null) {
            node = node.left;
            depth++;
        }
        return depth;
    }

    // Verify if node at index exists
    public boolean checkExistence(int index, int depth, TreeNode node) {
        int low = 0, high = (int)Math.pow(2, depth) - 1;
        int mid;
        for (int level = 0; level < depth; level++) {
            mid = low + (high - low) / 2;
            if (index <= mid) {
                node = node.left;
                high = mid;
            } else {
                node = node.right;
                low = mid + 1;
            }
        }
        return node != null;
    }

    public int countNodes(TreeNode rootNode) {
        if (rootNode == null) return 0;

        int treeDepth = findDepth(rootNode);
        if (treeDepth == 0) return 1;

        int leftBound = 1, rightBound = (int)Math.pow(2, treeDepth) - 1;
        int median;
        while (leftBound <= rightBound) {
            median = leftBound + (rightBound - leftBound) / 2;
            if (checkExistence(median, treeDepth, rootNode)) leftBound = median + 1;
            else rightBound = median - 1;
        }

        // Return total nodes calculated
        return (int)Math.pow(2, treeDepth) - 1 + leftBound;
    }
}

The provided Java code defines a solution to count the number of nodes in a complete binary tree. The implementation includes split functions to optimize the node count process through binary search, avoiding the need to traverse every node directly.

• depth calculation: The findDepth function measures the depth of the tree by traversing from the root node to the deepest leftmost node. This ensures logarithmic time complexity relative to the height of the tree, which is optimal for balanced trees.

• existence check: The checkExistence function determines whether a node exists at a specified index for a given depth. Utilizing binary search on the tree level, it strategically navigates right or left based upon the mid-point calculations, thereby facilitating direct access to potential nodes without exhaustive visiting.

• counting nodes: The main method, countNodes, utilizes the aforementioned helpers to efficiently count nodes. Initially, it handles the edge case of a null tree by immediately returning zero. Using the depth obtained from findDepth, it sets up a boundary for a binary search. The search narrows down the bounds to find the first nonexistent node index in the last level of the tree, therefore determining the count of existing nodes in less traversed paths.

This solution leverages logarithmic depth traversal combined with binary search over the last level of the tree, both contributing to significant performance gains particularly for large data sets where direct traversal would be computationally expensive. This method ensures an efficient and precise count of nodes in a complete binary tree.

class Solution:
    def tree_depth(self, node: TreeNode) -> int:
        depth = 0
        while node.left:
            node = node.left
            depth += 1
        return depth

    def node_exists(self, index: int, depth: int, node: TreeNode) -> bool:
        low, high = 0, 2**depth - 1
        for _ in range(depth):
            mid = low + (high - low) // 2
            if index <= mid:
                node = node.left
                high = mid
            else:
                node = node.right
                low = mid + 1
        return node is not None

    def countNodes(self, root: TreeNode) -> int:
        if not root:
            return 0
        
        depth = self.tree_depth(root)
        if depth == 0:
            return 1
        
        low, high = 1, 2**depth - 1
        while low <= high:
            mid = low + (high - low) // 2
            if self.node_exists(mid, depth, root):
                low = mid + 1
            else:
                high = mid - 1
        
        return (2**depth - 1) + low

The given Python 3 code efficiently solves the problem of counting the total number of nodes in a complete binary tree. The structure of the code comprises a main class Solution with three methods: tree_depth, node_exists, and countNodes.

• tree_depth(node): This method calculates the depth of the tree by traversing down the left child from the root until no left child is present. It returns the number of levels in the tree excluding the root level.

• node_exists(index, depth, node): This method determines whether a node exists at a specific index within the last level of the tree. It performs a binary search in the range of possible node indices at the deepest level, adjusting the search range based on whether the middle index node is found to be present or not.

• countNodes(root): This is the main method where:

  1. The tree's depth is computed.
  2. If the tree has no depth (meaning only the root node exists or no nodes at all), an appropriate count is returned.
  3. If the tree has more depth, it performs a binary search on the last level to find the last node index, using the logic defined in the node_exists method.
  4. The total number of nodes in the tree is then calculated by adding up the nodes from all levels except the last, with those identified in the last level of the tree.

This implementation is efficient because it optimizes the process of counting nodes in a complete binary tree through the use of binary search principles, reducing the potential overhead of a naive approach that would involve checking every node. This ensures high performance, especially pertinent for trees with a large number of levels.