Algorithm


Problem Name: 222. Count Complete Tree Nodes

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

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

Design an algorithm that runs in less than O(n) time complexity.

 

Example 1:

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

Example 2:

Input: root = []
Output: 0

Example 3:

Input: root = [1]
Output: 1

 

Constraints:

  • The number of nodes in the tree is in the range [0, 5 * 104].
  • 0 <= Node.val <= 5 * 104
  • The tree is guaranteed to be complete.

Code Examples

#1 Code Example with C Programming

Code - C Programming


void dfs(struct TreeNode *node, int i, int n, int *x) {
    if (i == n) {
        if (node->left) (*x) ++;
        if (node->right) (*x) ++;
        return;
    }
    
    if ((*x) % 2) return;
    dfs(node->left, i + 1, n, x);
    
    if ((*x) % 2) return;
    dfs(node->right, i + 1, n, x);    
}
int countNodes(struct TreeNode* root) {
    struct TreeNode *node = root;
    int i = 0;
    int x = 0;
    
    if (!node) return 0;
    
    while (node) {
        i ++;
        node = node->right;
    }

    dfs(root, 1, i, &x);
    
    return (1 << i) - 1 + x;
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
root = [1,2,3,4,5,6]

Output

x
+
cmd
6

#2 Code Example with Java Programming

Code - Java Programming


class Solution {
    public int countNodes(TreeNode root) {
        int leftDepth = getDepth(root, -1);
        int rightDepth = getDepth(root, 1);
        if (leftDepth == rightDepth) {
            return (1 << leftDepth) - 1;
        }
        return 1 + countNodes(root.left) + countNodes(root.right);
    }
    
    private int getDepth(TreeNode root, int dir) {
        int depth = 0;
        while (root != null) {
            depth++;
            if (dir == -1) {
                root =  root.left;
            } else {
                root = root.right;
            }
        }
        return depth;
    }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
root = [1,2,3,4,5,6]

Output

x
+
cmd
6

#3 Code Example with Javascript Programming

Code - Javascript Programming


const countNodes = function(root) {
  if (root == null) return 0;
  const payload = { depth: 0, numOfLast: 0, total: 0 };
  traverse([root], 0, payload);
  return payload.total;
};

function traverse(row, depth, obj) {
  const next = [];
  for (let i = 0; i  <  row.length; i++) {
    if (row[i].left) next.push(row[i].left);
    if (row[i].right) next.push(row[i].right);
  }
  if (Math.pow(2, depth + 1) !== next.length) {
    obj.total = Math.pow(2, depth + 1) - 1 + next.length;
    return;
  }
  if (next.length) traverse(next, depth + 1, obj);
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
root = []

#4 Code Example with Python Programming

Code - Python Programming


class Solution:
    
    def countNodes(self, root):
        if not root: return 0
        l = self.getDepth(root.left)
        r = self.getDepth(root.right)
        if l == r:
            return (1 << l) + self.countNodes(root.right)
        return (1 << r) + self.countNodes(root.left)
    
    def getDepth(self, root):
        if not root: return 0
        return 1 + self.getDepth(root.left)
Copy The Code & Try With Live Editor

Input

x
+
cmd
root = []

#5 Code Example with C# Programming

Code - C# Programming


using System;

namespace LeetCode
{
    public class _0222_CountCompleteTreeNodes
    {
        public int CountNodes(TreeNode root)
        {
            if (root == null) { return 0; }

            // Find Depth
            var current = root;
            var depth = 0;
            while (current.left != null)
            {
                current = current.left;
                depth++;
            }

            if (depth == 0) return 1;

            var count = (int)Math.Pow(2, depth) - 1;

            var l = 0;
            var r = count;
            while (l  < = r)
            {
                var mid = l + (r - l) / 2;
                if (FindNode(root, mid, count, depth))
                    l = mid + 1;
                else
                    r = mid - 1;
            }

            return count + l;
        }

        public bool FindNode(TreeNode root, int index, int count, int depth)
        {
            var l = 0;
            var r = count;
            for (int i = 0; i  <  depth; i++)
            {
                var mid = l + (r - l) / 2;
                if (index  < = mid)
                {
                    root = root.left;
                    r = mid;
                }
                else
                {
                    root = root.right;
                    l = mid + 1;
                }
            }
            return root != null;
        }
    }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
root = [1]

Output

x
+
cmd
1
Advertisements

Demonstration


Previous
#221 Leetcode Maximal Square Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#223 Leetcode Rectangle Area Solution in C, C++, Java, JavaScript, Python, C# Leetcode