CareerCup

If we are talking about a binary search tree where the following holds true,

left 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.

what is the exact meaning of wellordered BT??

A tree by itself cant be ordered( plz correct me if i am wrong).The output from the traversals show whether it results in ascending sorted manner or not (i.e inorder traversal of BST). So its the traversal not the tree

yeah... well-ordered? what does that mean? do you mean a balanced-tree?

Assuming 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;
}

Well ordered ... mmm...
As long as a BT follows one of Pre, In, Post-Order, it is well ordered.
So one of three traverse ways should generate a monotonic sequence.
Just my guess hehe

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;
}

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 tiger

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;
}

well ordered=monotonic inorder?

well ordered is when all the leaf nodes are at the same depth or max 1 level apart, isnt it?!?!?!!??!?!?!?!?!

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 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);
	}