Leetcode

Count Complete Tree Nodes

Approach 1: Naive

  • Time:O(n)
  • Space:O(h)

C++

class Solution {
 public:
  int countNodes(TreeNode* root) {
    if (!root)
      return 0;
    return 1 + countNodes(root->left) + countNodes(root->right);
  }
};

JAVA

class Solution {
  public int countNodes(TreeNode root) {
    if (root == null)
      return 0;
    return 1 + countNodes(root.left) + countNodes(root.right);
  }
}

Python

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)

C++

class Solution {
 public:
  int countNodes(TreeNode* root) {
    if (!root)
      return 0;

    TreeNode* l = root;
    TreeNode* r = root;
    int heightL = 0;
    int heightR = 0;

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

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

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

JAVA

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

    TreeNode l = root;
    TreeNode r = root;
    int heightL = 0;
    int heightR = 0;

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

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

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

Python

class Solution:
  def countNodes(self, root: Optional[TreeNode]) -> int:
    if not root:
      return 0

    l = root
    r = root
    heightL = 0
    heightR = 0

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

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

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