Leetcode Problem 222. Count Complete Tree Nodes

222. Count Complete Tree Nodes

Leetcode Solutions

Binary Search on the Last Level of a Complete Binary Tree

  1. If the tree is empty, return 0.
  2. Compute the depth d of the tree (distance from the root to the deepest node).
  3. If d is 0, meaning the tree has only one node, return 1.
  4. Calculate the number of nodes in all levels except the last, which is 2^d - 1.
  5. Perform a binary search on the last level to find the count of nodes. For each node index, use a helper function exists to check if a node at that index exists.
  6. The exists function will simulate the path from the root to the node index and check if the node is present.
  7. Return the total number of nodes, which is 2^d - 1 plus the number of nodes found in the last level.
UML Thumbnail

Linear Time Recursive Node Count

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...