Skip to content

222. Count Complete Tree Nodes 👍

Approach 1: Naive

  • Time: $O(n)$
  • Space: $O(h)$
1
2
3
4
5
6
7
8
class Solution {
 public:
  int countNodes(TreeNode* root) {
    if (root == nullptr)
      return 0;
    return 1 + countNodes(root->left) + countNodes(root->right);
  }
};

1
2
3
4
5
6
7
class Solution {
  public int countNodes(TreeNode root) {
    if (root == null)
      return 0;
    return 1 + countNodes(root.left) + countNodes(root.right);
  }
}

1
2
3
4
5
class Solution:
  def countNodes(self, root: Optional[TreeNode]) -> int:
    if not root:
      return 0
    return 1 + self.countNodes(root.left) + self.countNodes(root.right)

Approach 2: Heuristic

  • Time: $O(\log^2n)$
  • Space: $O(h)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
 public:
  int countNodes(TreeNode* root) {
    if (root == nullptr)
      return 0;

    TreeNode* left = root;
    TreeNode* right = root;
    int heightL = 0;
    int heightR = 0;

    while (left != nullptr) {
      ++heightL;
      left = left->left;
    }

    while (right != nullptr) {
      ++heightR;
      right = right->right;
    }

    if (heightL == heightR)  // `root` is a complete tree.
      return pow(2, heightL) - 1;
    return 1 + countNodes(root->left) + countNodes(root->right);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
  public int countNodes(TreeNode root) {
    if (root == null)
      return 0;

    TreeNode left = root;
    TreeNode right = root;
    int heightL = 0;
    int heightR = 0;

    while (left != null) {
      ++heightL;
      left = left.left;
    }

    while (right != null) {
      ++heightR;
      right = right.right;
    }

    if (heightL == heightR) // `root` is a complete tree.
      return (int) Math.pow(2, heightL) - 1;
    return 1 + countNodes(root.left) + countNodes(root.right);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
  def countNodes(self, root: Optional[TreeNode]) -> int:
    if not root:
      return 0

    left = root
    right = root
    heightL = 0
    heightR = 0

    while left:
      heightL += 1
      left = left.left

    while right:
      heightR += 1
      right = right.right

    if heightL == heightR:  # `root` is a complete tree.
      return pow(2, heightL) - 1
    return 1 + self.countNodes(root.left) + self.countNodes(root.right)