Scale Engineer

Count Complete Tree Nodes

Easy
#0210Time: O(n) where n is the number of nodes in the treeSpace: O(h) where h is the height of the tree, due to recursive call stack1 company
Patterns
Bit Manipulation
Algorithms
Binary Search
Data structures
TreeBinary Tree
Companies
Dunzo

Prompt

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.

Approaches

3 approaches with complexity analysis and trade-offs.

The most straightforward approach is to traverse the entire tree using DFS (Depth First Search) and count all nodes.

Algorithm

  1. If root is null, return 0
  2. Recursively count nodes in left subtree
  3. Recursively count nodes in right subtree
  4. Return 1 (current node) + left count + right count

Walkthrough

We can use a simple recursive DFS approach to traverse through all nodes of the tree. For each node, we add 1 to our count and recursively process the left and right children.

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

This solution will visit every node exactly once. While simple to implement, it doesn't take advantage of the complete binary tree property.

Complexity

Time

O(n) where n is the number of nodes in the tree

Space

O(h) where h is the height of the tree, due to recursive call stack

Trade-offs

Pros

  • Simple to implement

  • Works for any binary tree

  • Easy to understand

Cons

  • Doesn't utilize the complete binary tree property

  • Visits every node in the tree

  • Not optimal for complete binary trees

Solutions

/** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) { * this.val = val; * this.left = left; * this.right = right; * } * } */ public class Solution { public int CountNodes ( TreeNode root ) { if ( root == null ) { return 0 ; } int left = depth ( root . left ); int right = depth ( root . right ); if ( left == right ) { return ( 1 << left ) + CountNodes ( root . right ); } return ( 1 << right ) + CountNodes ( root . left ); } private int depth ( TreeNode root ) { int d = 0 ; for (; root != null ; root = root . left ) { ++ d ; } return d ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem