algoadvance

Leetcode 222. Count Complete Tree Nodes

Problem Statement

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

In a complete binary tree, every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2^h nodes inclusive at the last level h.

Example:

Input: root = [1,2,3,4,5,6]
Output: 6

Constraints:

Clarifying Questions

  1. Q: Is the tree necessarily balanced since it’s complete? A: No, a complete binary tree is not necessarily balanced, but every level, except possibly the last, is completely filled.

  2. Q: Can the input be null (i.e., an empty tree)? A: Yes, the tree can be empty which should return 0 nodes.

  3. Q: What should the output be for an empty tree? A: The output should be 0.

Strategy

Given that the tree is a complete binary tree, we can use the properties of such trees to count nodes more efficiently than a simple traversal:

  1. Height Calculation: In a complete tree, we determine the height of the tree by repeatedly following the left child.
  2. Binary Search on Last Level:
    • Perform a binary search on the possible node positions in the last level to determine how many nodes are there.
    • This leverages the properties of the complete tree to reduce the complexity.

The actual approach involves:

  1. Calculating the height of the tree.
  2. Using binary search to count the nodes in the last level, adjusting based on the presence of left and right sub-trees.

Code

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) return 0;

        int height = getHeight(root);
        if (height == 0) return 1;

        int upperCount = (1 << height) - 1;  // Nodes above the last level
        int left = 0, right = upperCount;

        while (left < right) {
            int idxToFind = (right - left + 1) / 2 + left;
            if (nodeExists(idxToFind, height, root)) {
                left = idxToFind;
            } else {
                right = idxToFind - 1;
            }
        }

        return upperCount + left + 1;
    }

    private int getHeight(TreeNode root) {
        int height = 0;
        while (root.left != null) {
            height++;
            root = root.left;
        }
        return height;
    }

    private boolean nodeExists(int idxToFind, int height, TreeNode node) {
        int left = 0, right = (1 << height) - 1;
        int count = 0;

        while (count < height) {
            int middle = (right - left + 1) / 2 + left;
            if (idxToFind >= middle) {
                node = node.right;
                left = middle;
            } else {
                node = node.left;
                right = middle - 1;
            }
            count++;
        }

        return node != null;
    }
}

Time Complexity

Thus, the total time complexity is (O((\log N)^2)).

This approach is efficient given the constraint where N can be up to (5 \times 10^4).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI