Microsoft Interview Question
Software Engineer / DevelopersAssuming that its a BST. I think the following code should do it :
void RetInfixArray(node* parent, int arr[])
{
static int index = 0;
if(parent == null)
return;
RetInfixArray(node->left);
arr[index++] = node->data;
RetInfixArray(node->right);
}
int IsBalanced(node *root)
{
int* arr;
int length = 0;
if(!root)
return;
//use some method to find the number of nodes of the BT
length = NodesNum(root);
arr = (int *) malloc(sizeof(int) * length);
if(!arr)
return;
RetInfixArray(root, arr);
for(i = 0;i <length-1;i++)
{
if(arr[i]>arr[i+1])
return 0;
}
return 1;
}
bool verifyBST(Node* aNode)
{
if((aNode->left) && (aNode->left->value > aNode->value))
return false;
if((aNode->right) && (aNode->right->value < aNode->value))
return false;
verifyBST(aNode->left);
verifyBST(aNode->right);
return true;
}
Your idea is good, but there is some minor bug in your code. I modified it.
boolean verifyBST(Node* aNode)
{
if((aNode->left) && (aNode->left->value > aNode->value))
return false;
if((aNode->right) && (aNode->right->value < aNode->value))
return false;
if(!(aNode->left&&aNode->right)) return true;
else {
if(verifyBST(aNode->left) && verifyBST(aNode->right))
return true;
else
return false;
}
}
I just found that there is some bug even in the idea. ;-)
for example, the following tree will return true for your code.
5
/ \
3 9
/ \ / \
1 6 4 10
I think the problem just want you to check whether this tree is a BST or not.
bool isBSTHelper(BinaryTree *p, int low, int high) {
if (!p) return true;
if (low < p->data && p->data < high)
return isBSTHelper(p->left, low, p->data) &&
isBSTHelper(p->right, p->data, high);
else
return false;
}
bool isBST(BinaryTree *root) {
// INT_MIN and INT_MAX are defined in C++'s <climits> library
return isBSTHelper(root, INT_MIN, INT_MAX);
}
looking only at left and right children will not prove that it is well ordered. We need to see the ordering of all the nodes during an inorder traversal.
Here is a code to check for well ordered property.
bool well_ordered(node *root)
{
int largest;
if (!root)
return true;
else
return inorder(root,largest);
}
bool inorder(node *root, int &largest)
{
int left,right;
bool result;
largest = root->data;
if (root->left) {
result = inorder(root->left,left);
if (!result) return false;
if (left > largest) return false;
}
if (root->right) {
result = inorder(root->right,right);
if (!result) return false;
if (largest > right) return false;
else largest = right;
}
return true;
}
Good idea, but I doubt your algo can fix the issue brought up by Nirvanatiger.
Let's say in your recursion we are at the *root=5 levle, and look at the right branch. largest=5, and
result=true, and largest(5)<right(10), so it will return true. However, it should return false. The point is:
1. when comparing the left brach, you should assert(currentNode.value>left.largest)
2. when comparing the right brach, assert ((currentNode.value<right.smallest)), note it is the smallest other than largest.
You got the first comparison right, but the 2nd comparison wrong.
To continue with my comment posted to NM on Tuesday September 23, 2008, here is a inefficient algo, I believe the LeftLargest and RightSmallest function can be saved with some reference parameters.
Anyway, I just leave it as is because it looks more straightforward and understandable.
========================================================
//find the largest value in the left brach.
int LeftLargest(Node* root)
{
..if (root->left==NULL)
....return root->value;
..Node* left=root->left;
..while (left->right)
....left=left->right;
..return left->value;
}
//find the smallest value in the right brach.
int RightSmallest(Node* root)
{
..if (root->right==NULL)
....return root->value;
..Node* right=root->right;
..while (right->left)
....right=right->left;
..return right->value;
}
//compare
bool compare(Node* root){
..if ((root->value >= LeftLargest(root))&&
....(root->value <= RightSmallest(root)))
......return true;
..else
....return false;
}
bool postOrder(Node* root)
{
..if (!root)
....return true;
..else if (postOrder(root->left) && postOrder(root->right) && compare(root))
....return true;
..else
......return false;
}
I think the following algo will work though written in C#
/// <summary>
///
/// </summary>
/// <param name="node"></param>
/// <returns></returns>
public bool IsBST(Node node)
{
if (node == null)
return true;
else
{
if (!IsBSTUtil(node))
return false;
}
return true;
}
/// <summary>
/// /
/// </summary>
/// <param name="node"></param>
/// <param name="data"></param>
/// <returns></returns>
public bool IsBSTUtil(Node node)
{
if (node == null)
return true;
else
{
if (node.Left != null && node.Left.Data > node.Data)
return false;
if (node.Right != null && node.Right.Data <= node.Data)
return false;
if (!IsBSTUtil(node.Left) || !IsBSTUtil(node.Right))
return false;
}
return true;
}
// Method to check if binary tree is actually a binary search tree
// Check if the max in the left tree is is less than root node
// Check if the min in the right tree is greater than the root node
// Do this sort of validation for all the nodes.
// Not a better approach as we are calling max and min for each and every
// node
public Integer maxValue(binaryTreeNode b) {
if (b == null)
return 0;
return Math.max(Math.max(maxValue(b.left), maxValue(b.right)), b.value);
}
public Integer minValue(binaryTreeNode b) {
if (b == null)
return Integer.MAX_VALUE;
return Math.min(Math.min(minValue(b.left), minValue(b.right)), b.value);
}
public boolean isBST_1() {
return isBST_1(root);
}
public boolean isBST_1(binaryTreeNode b) {
if (b == null)
return true;
if (b.left != null && b.value <= maxValue(b.left))
return false;
if (b.right != null && b.value >= minValue(b.right))
return false;
return isBST_1(b.left) && isBST_1(b.right);
}
// Making sure number of traversals are less
public boolean isBST_2() {
return isBST_2(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
public boolean isBST_2(binaryTreeNode b, int min, int max) {
if (b == null)
return true;
if (b.value >= max || b.value <= min)
return false;
return isBST_2(b.left, min, b.value) && isBST_2(b.right, b.value, max);
}
// Making sure number of traversals are less than previous approach
public boolean isBST_2() {
return isBST_2(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
public boolean isBST_2(binaryTreeNode b, int min, int max) {
if (b == null)
return true;
if (b.value >= max || b.value <= min)
return false;
return isBST_2(b.left, min, b.value) && isBST_2(b.right, b.value, max);
}
// Making sure number of traversals are less
public boolean isBST_2() {
return isBST_2(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
public boolean isBST_2(binaryTreeNode b, int min, int max) {
if (b == null)
return true;
if (b.value >= max || b.value <= min)
return false;
return isBST_2(b.left, min, b.value) && isBST_2(b.right, b.value, max);
}
If we are talking about a binary search tree where the following holds true,
- srihari January 06, 2006left child value <= parent value < right child value
then, an in-order tree walk would give us a sorted list. If we verify that the list is in non-decreasing order then we are done.