# C# accepted recursive

• The count of nodes in complete binary tree is formed by two parts:

1. All nodes except the last layer: 2 ^ (treeDepth - 1) - 1;

2. nodes on the last layer:

for this part, we use a recusive divide and conquer method, CountLastLayerNodes, as shown below:

``````    public int CountNodes(TreeNode root)
{
if (root == null)
{
return 0;
}
if (root.left == null && root.right == null)
{
return 1;
}

int leftDepth = GetLeftDepth(root);
int nodeCountWithoutLastLayer = (int)Math.Pow(2, leftDepth) - 1;
int nodeCountOnLastLayer = CountLastLayerNodes(root);
return (nodeCountWithoutLastLayer + nodeCountOnLastLayer);
}

public static int CountLastLayerNodes(TreeNode root)
{
int count = 0;
if (root == null)
{
return count;
}

if (root.left == null && root.right == null)
{
return 0;
}

if (root.left != null && root.right == null)
{
return 1;
}

int leftleftDepth = GetLeftDepth(root.left);
int leftrightDepth = GetRightDepth(root.left);
int rightleftDepth = GetLeftDepth(root.right);
int rightrightDepth = GetRightDepth(root.right);

if (leftleftDepth == rightrightDepth)
{
return (int)Math.Pow(2, leftleftDepth + 1);
}
else if (leftleftDepth == rightleftDepth)
{
return (int)Math.Pow(2, leftleftDepth) + CountLastLayerNodes(root.right);
}
else if (leftleftDepth == leftrightDepth)
{
return (int)Math.Pow(2, leftleftDepth);
}
else
{
return CountLastLayerNodes(root.left);
}
}

public static int GetLeftDepth(TreeNode node)
{
TreeNode temp = node;
int depth = 0;
while (temp != null)
{
if (temp.left != null)
{
temp = temp.left;
depth++;
}
else
{
break;
}
}
return depth;
}

public static int GetRightDepth(TreeNode node)
{
TreeNode temp = node;
int depth = 0;
while (temp != null)
{
if (temp.right != null)
{
temp = temp.right;
depth++;
}
else
{
break;
}
}
return depth;
}``````

• Saw others' code, seems this one is easier to understand:

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

int leftDepth = GetLeftDepth(root);
int rightDepth = GetRightDepth(root);
if (leftDepth == rightDepth)
{
return (int)Math.Pow(2, leftDepth + 1) - 1;
}
else
{
return (1 + CountNodes(root.left) + CountNodes(root.right));
}
}``````

• Combine 1st post and 2nd post it should work.

Finally a answer not using Shift operator. I find shift operators are less human readable, though it's fast and lead TLE....but I think it's OK for interviewing.
You could combine GetLeftDepth() and GetRightDepth into GetDpeth()

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.