Problem: Given a level-order sorted complete binary tree, the task is to check whether a key exists in it or not.
Approach: We can traverse the tree and get the element but that will take linear time. Let's see how can we use level-order sorted property.
One immediate approach was to first the get the level in which the target element may exist. To get to that level is easy. We can go to the first number of a particular level that means the left most node of that level and whenever we see that the value at the left most node of a level is greater than target than the previous level is the level where the target might exist.
Once we get the level, we can use binary search to find the target on that level. The only problem is we just can't access the elements at a level like array so now our problem is how to get a number at an index. For that we can use Gray code.
That's all!
Implementation in C#:
public bool FintNumInLevelOrderSortedBinaryTree(int num)
{
bool numFound = false;
int level = this.FindTargetLevel(num, ref numFound);
if (numFound)
{
return true;
}
if (level == -1)
{
return false;
}
return this.FintNumAtLevelBinarySearch(level, 0, (int)Math.Pow(2, level) - 1, num);
}
private bool FintNumAtLevelBinarySearch(int level, int low, int high, int num)
{
if (low <= high)
{
int mid = (low + high) / 2;
int[] grayCode = this.GenerateGrayCode(mid, level);
int elementAtMid = this.GetElementAtIndex(grayCode);
if (elementAtMid == -1)
{
return this.FintNumAtLevelBinarySearch(level, low, mid - 1, num);
}
if (elementAtMid == num)
{
return true;
}
if (elementAtMid < num)
{
return this.FintNumAtLevelBinarySearch(level, mid + 1, high, num);
}
else
{
return this.FintNumAtLevelBinarySearch(level, low, mid - 1, num);
}
}
return false;
}
private int GetElementAtIndex(int[] grayCode)
{
BinaryTreeNode node = this.Root;
for (int i = 0; i < grayCode.Length; ++i)
{
if (grayCode[i] == 0)
{
if (node.LeftNode == null)
{
return -1;
}
node = node.LeftNode;
}
else
{
if (node.RightNode == null)
{
return -1;
}
node = node.RightNode;
}
}
return node.Value;
}
private int[] GenerateGrayCode(int num, int numOfBits)
{
int[] grayCode = new int[numOfBits];
int i = grayCode.Length - 1;
while(num != 0)
{
grayCode[i--] = num % 2;
num /= 2;
}
for (; i >= 0; --i)
{
grayCode[i] = 0;
}
return grayCode;
}
private int FindTargetLevel(int num, ref bool numFound)
{
if (num < this.Root.Value)
{
return -1;
}
if (num == this.Root.Value)
{
numFound = true;
return 0;
}
int currLevel = 0;
BinaryTreeNode node = this.Root;
while(node.LeftNode != null && node.LeftNode.Value < num)
{
++currLevel;
if (node.LeftNode.Value == num)
{
numFound = true;
return currLevel;
}
node = node.LeftNode;
}
return currLevel;
}
Complexity: O((logn)^2)
No comments:
Post a Comment