Problem: Given the root of a complete binary tree, return the number of the nodes in the tree. A complete binary tree is completely filled except the last level. All nodes in the last level are as far left as possible.
Approach: We could have a linear time approach and count the nodes using any traversal like following:
- CountNode(TreeNode node)
- IF node == null
- RETURN 0
- RETURN 1 + CALL CountNode(node.Left) + CALL CountNode(node.Right)
But here we are not taking the advantage of given binary tree being a complete binary tree. We know that all the levels except last level will be completely filled. That means if the depth of the tree is d then we know that we will get 2 ^ d - 1 nodes for sure. Now we just need to add the number of nodes in the last level to this and it will be our answer.
Now the question is how to get the number of nodes at the last level. We know that all the nodes at this level will be as far left as possible. That means we can apply the binary search here which we used to find the element in level order sorted complete binary tree using the gray code.
That's all!
Implementation in C#:
public int CountNodes()
{
if (this.Root == null)
{
return 0;
}
int depth = this.GetDepth();
if (depth == 0)
{
return 1;
}
int leftNodesAtLastLevel = this.CountNodesAtLastLevelBinarySearch(depth, 0, (int)Math.Pow(2, depth) - 1);
return (int)Math.Pow(2, depth) - 1 + leftNodesAtLastLevel;
}
private int CountNodesAtLastLevelBinarySearch(int level, int left, int right)
{
while (left <= right)
{
int mid = (left + right) / 2;
if (this.GetNodeAtIndex(mid, level) != null)
{
left = mid + 1;
}
else
{
right = mid - 1;
}
}
return left;
}
private BinaryTreeNode GetNodeAtIndex(int index, int level)
{
int[] grayCode = this.GetGrayCode(index, level);
BinaryTreeNode node = this.Root;
for (int i = 0; i < level; ++i)
{
if (grayCode[i] == 0)
{
node = node.LeftNode;
}
else
{
node = node.RightNode;
}
}
return node;
}
private int[] GetGrayCode(int index, int numOfBits)
{
int[] grayCode = new int[numOfBits];
int i = numOfBits - 1;
while (index > 0)
{
grayCode[i--] = index % 2;
index /= 2;
}
return grayCode;
}
private int GetDepth()
{
BinaryTreeNode node = this.Root;
int depth = 0;
while (node.LeftNode != null)
{
node = node.LeftNode;
++depth;
}
return depth;
}
Complexity: O((logn)^2) where n is number of nodes so logn is depth of the tree.
No comments:
Post a Comment