Problem

Given a binary tree, Write an non-recursive algorithm to find the size of the tree.

Examples

Example 1:

1
2
3
4
5
6
7
8
9

 Input: 
     Tree:  
         1
        / \
       2   3
 Output: 
     3
 Explanation: 
     The tree has 3 nodes — 1, 2, and 3.

Solution

Method 1 - Recursion

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {  
   // Function to compute the size of the binary tree  
   public int size(TreeNode root) {  
       if (root == null) {  
           return 0;  
       }  
       return 1 + size(root.left) + size(root.right);  
   }  

   public static void main(String[] args) {  
       Solution solution = new Solution();  
       TreeNode root = new TreeNode(1);  
       root.left = new TreeNode(2);  
       root.right = new TreeNode(3);  

       System.out.println("Size of the tree: " + solution.size(root));  // Output: 3  
   }  
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:  
   # Function to compute the size of the binary tree  
   def size(self, root):  
       if root is None:  
           return 0  
       return 1 + self.size(root.left) + self.size(root.right)  

# Testing the solution  
if __name__ == "__main__":  
   solution = Solution()  
   root = Solution.TreeNode(1)  
   root.left = Solution.TreeNode(2)  
   root.right = Solution.TreeNode(3)  

   print("Size of the tree:", solution.size(root))  # Output: 3

Complexity

  • ⏰ Time complexity: O(n). Since we are visiting each node exactly once, the time complexity is linear in terms of the number of nodes (n).
  • 🧺 Space complexity: O(h). The space complexity depends on the height (h) of the tree, since the recursive call stack will store functions up to the height of the tree.

Method 2 - BFS

Instead of using recursion (DFS), we can solve this problem iteratively using Breadth-First Search (BFS). BFS traverses the tree level by level using a queue, and while visiting each node, we count it. This approach avoids stack recursion and handles the traversal explicitly using a queue. To find the size of the binary tree using BFS:

  1. Use a queue to store nodes for level-order traversal.
  2. Start by enqueueing the root node.
  3. For each node in the queue:
    • Dequeue the node, visit it, and increment the size count.
    • If the node has a left child, enqueue it.
    • If the node has a right child, enqueue it.
  4. Continue this process until the queue is empty.
  5. Return the total count, which represents the size of the tree.

Code

 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
27
28
29
30
31
32
33
34
35
36

class Solution {
    // Function to compute the size of the binary tree using BFS
    public int size(TreeNode root) {
        if (root == null) {
            return 0; // If the tree is empty
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int size = 0;

        while (!queue.isEmpty()) {
            TreeNode current = queue.poll();
            size++; // Increment the size for the current node

            // Add children to the queue
            if (current.left != null) {
                queue.add(current.left);
            }
            if (current.right != null) {
                queue.add(current.right);
            }
        }

        return size; // Total count of nodes
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);

        System.out.println("Size of the tree: " + solution.size(root)); // Output: 3
    }
}
 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
27
28
29

class Solution:
    # Function to compute the size of the binary tree using BFS
    def size(self, root):
        if not root:
            return 0  # If the tree is empty
        
        queue = deque([root])  # Initialize the queue with the root node
        size = 0

        while queue:
            current = queue.popleft()  # Dequeue the current node
            size += 1  # Increment the size for the current node
            
            # Add children to the queue
            if current.left:
                queue.append(current.left)
            if current.right:
                queue.append(current.right)

        return size  # Total count of nodes

# Testing the solution
if __name__ == "__main__":
    solution = Solution()
    root = Solution.TreeNode(1)
    root.left = Solution.TreeNode(2)
    root.right = Solution.TreeNode(3)

    print("Size of the tree:", solution.size(root))  # Output: 3

Complexity

  • ⏰ Time complexity: O(n). Each node is visited exactly once.
  • 🧺 Space complexity: O(n). The maximum number of nodes stored in the queue at one time is equal to the width w of the tree at its maximum.