How to count a binary tree size
Given a
binary tree
, return binary treesize
Note :
Size
of thebinary tree
is number of nodes in thetree
/* 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
Recent articles
Nice to read