How to count a binary tree size

Given a binary tree, return binary tree size

Note : Size of the binary tree is number of nodes in the tree

/* Definition for TreeNode
public class TreeNode
{
    public int Value;
    public TreeNode Left;
    public TreeNode Right;

    public TreeNode(int value)
    {
        Value = value;
    }
}
*/
public class Solution
{
    public int Size(TreeNode root)
    {
    }
}

Example

Output: 6

/* Definition for TreeNode
public class TreeNode
{
    public int Value;
    public TreeNode Left;
    public TreeNode Right;

    public TreeNode(int value)
    {
        Value = value;
    }
}
*/
public sealed class Solution
{
    public int Size(TreeNode root)
    {
    }
}

Approach:

Almost all binary tree problems can be solved using recursion or without it. Let's use recursion for this one.

The tree size can be represented as: 1 (for the root) + size of the left subtree + size of the right subtree. Size of the left subtree and the right subtree can be found recursively.

Code

    public int Size(TreeNode root)
    {
        if (root == null)
        {
            return 0;
        }

        return Size(root.Left) + Size(root.Right) + 1;
    }

Time Complexity: O(n)

Video Lesson