Size of Binary Tree

Problem

Given a binary tree of size n, you have to count the number of nodes in it. For example, the count of nodes in the tree below is 4.

      1
     / \
   10   39
  /
5

Examples:

Example 1:

Input:
1 2 3
Output:
3
Explanation:
Given Tree is :
                              1
                             / \
                            2   3
There are 3 nodes in the tree.

Example 2:

Input:
10 5 9 N 1 3 6 
Output:
6
Explanation:
Given Tree is :
                              10
                             /  \
                           5     9
                            \    / \
                             1  3   6
There are 6 nodes in the tree.

Your task:

You don't need to read input or print anything. Your task is to complete the function getSize() which takes the tree head node and returns an integer representing the number of nodes in the tree.

• Expected Time Complexity: $O(n)$
• Expected Auxiliary Space: $O(h)$, where h is the height of the binary tree

Constraints:

• $1<=n<=10^5$
• $1 <=$ values of nodes $<= 10^6$

Solution

Python

def getSize(self, node : Optional['Node']) -> int:
    if node is None:
        return 0
    else:
        return self.getSize(node.left) + 1 + self.getSize(node.right)

Java

public static int getSize(Node node) {
    if(node==null)
        return 0;
    else
        return getSize(node.left) + 1 + getSize(node.right);
}

C++

int getSize(Node* node) {
    if (node == nullptr)
        return 0;
    else
        return getSize(node->left) + 1 + getSize(node->right);
}

C

int getSize(struct Node* node) {
    if (node == NULL)
        return 0;
    else
        return getSize(node->left) + 1 + getSize(node->right);
}

• Time Complexity: $O(n)$
• Auxiliary Space: $O(h)$