wdxcn1123
BAN USERIf a tree meets the requirement to be a binary search tree , then for every node of that tree, these nodes must satisfied that every nodes in left sub-tree of that node must smaller than that node and its right sub-nodes must bigger or equivalent , vice verse.
So, we can get the maximum and minimum value of the sub-trees for every node recursively.It will cost O(n) time if it have n nodes in tree.
And then , for every nodes , checking whether the maximum value of its left node is smaller than its and also the minimum value of its right node . It also cost O(n) time.If all nodes passed this check , the tree is binary search tree .
this is pseudo-code for getting maximum and minimum values for nodes.
void getMaxMin(node cur)
{
if (cur.isLeaf())
{
maxi[cur] = cur.value;
mini[cur]=cur.value
return ;
}
getMaxMin(cur.left);
getMaxMin(cur.right);
maxi[cur] = max(maxi[cur.left],maxi[cur.right]);
mini[cur] = min(mini[cur.left],mini[cur.right]);
}
newton iterate method
- wdxcn1123 September 06, 2012