Thursday, January 26, 2012

No. 31 - Binary Search Tree Verification


Question: How to verify whether a binary tree is a binary search tree?

For example, the tree in Figure 1 is a binary search tree.
Figure 1: A binary search tree

A node in binary tree is defined as:

struct BinaryTreeNode
{
    int                    nValue;
    BinaryTreeNode*        pLeft; 
    BinaryTreeNode*        pRight;
};

Analysis: Binary search tree is an important data structure. It has a specific character: Each node is greater than or equal to nodes in its left sub-tree, and less than or equal to nodes in its right sub-tree. 

Solution 1: Verify value range of each node

If a binary search tree is scanned with pre-order traversal algorithm, the value in a root node is accessed to at first. After the root node is visited, it begins to scan nodes in the left sub-tree. The value of left sub-tree nodes should be less than or equal to the value of the root node. If value of a left sub-tree node is greater than the value of the root node, it violates the definition of binary search tree. It is similar for the right sub-tree.

Therefore, when it visits a node in binary search tree, it narrows the value range of left sub-tree and right sub-tree under the current visited node. All nodes are visited with the pre-order traversal algorithm, and their value is verified. If value in any node violates its corresponding range, it is not a binary search tree.

The following sample code is implemented based on this pre-order traversal solution:

bool isBST_Solution1(BinaryTreeNode* pRoot)
{
    int min = numeric_limits<int>::min();
    int max = numeric_limits<int>::max();
    return isBSTCore_Solution1(pRoot, min, max);
}

bool isBSTCore_Solution1(BinaryTreeNode* pRoot, int min, int max)
{
    if(pRoot == NULL)
        return true;

    if(pRoot->nValue < min || pRoot->nValue > max)
        return false;

    return isBSTCore_Solution1(pRoot->pLeft, min, pRoot->nValue)
        && isBSTCore_Solution1(pRoot->pRight, pRoot->nValue, max);
}

In the code above, value of each node should be in the range between min and max. The value of the current visited node is the maximal value of its left sub-tree, and the minimal value of its right sub-tree, so it updates the min and max arguments and verifies sub-trees recursively.

Solution 2: Increasing in-order traversal sequence

The first solution is based on pre-order traversal algorithm. Let us have another try on in-order traversal. The in-order traversal sequence of the binary search tree in Figure 1 is: 4, 6, 8, 10, 12, 14 and 16. It is noticeable that the sequence is increasingly sorted.

Therefore, a new solution is available: Nodes in a binary tree is scanned with in-order traversal, and compare value of each node against the value of the previously visited node. If the value of the previously visited node is greater than the value of current node, it breaks the definition of binary tree.

This solution might be implemented in C++ as the following code:

 bool isBST_Solution2(BinaryTreeNode* pRoot)
{
    int prev = numeric_limits<int>::min();
    return isBSTCore_Solution2(pRoot, prev);
}

bool isBSTCore_Solution2(BinaryTreeNode* pRoot, int& prev)
{
    if(pRoot == NULL)
        return true;

    return isBSTCore_Solution2(pRoot->pLeft, prev) // previous node
        && (pRoot->nValue >= prev) // current node
        && isBSTCore_Solution2(pRoot->pRight, prev = pRoot->nValue); // next node
}

The argument prev of the function isBSTCore_Solution2 above is the value of the previously visited node in pre_order traversal.

The discussion about this problem is included in my book <Coding Interviews: Questions, Analysis & Solutions>, with some revisions. You may find the details of this book on Amazon.com, or Apress.
 
The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages,  please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact him via zhedahht@gmail.com . Thanks.  
Posted by at
Labels: , , , , ,

15 comments:

  1. UnknownJanuary 26, 2012 at 2:53 PM

    According to me Second Soln doesnt work.
    Testcase:
    -----100
    --50
    ----150
    (100->left=50; 50->right=150)
    It should be like some thing like this:

    bool isBST(Node* root,int &prev) // prev=INT_MIN
    {
    if(!pNode)
    return true;
    return isBSTCore_Solution2(pRoot->m_pLeft,prev) && (pRoot->m_nValue >= prev)
    && (prev=pRoot->mValue || true) // Update prev
    && isBSTCore_Solution2(pRoot->m_pRight,prev);
    }

    ReplyDelete
    Replies
    1. Harry HeJanuary 28, 2012 at 11:18 AM

      Thanks for devendraiit's comments. It is correct that the argument for prev should be passed by reference. I have modified my code in the post.

      Delete
    2. nishiFebruary 20, 2012 at 8:04 PM

      Best way to find that IsBST()
      1. Travel in-order and store the elements in an array.
      2. if the array is sorted then its a BST otherwise not.

      Nishikant Sahu

      Delete
    3. UnknownJune 27, 2017 at 1:36 PM

      But order of n space complexity:(

      Delete
  2. UnknownSeptember 10, 2013 at 6:41 AM

    Why can't you just preorder walk the tree and confirm at each step that the left node (if it exists) is less than the parent, and the right node (if it exists) is greater than the parent?

    ReplyDelete
    Replies
    1. UnknownSeptember 11, 2013 at 1:21 AM

      what about ancestors..?u can't keep track of them with your current proposed method.

      Delete
    2. UnknownSeptember 11, 2013 at 3:58 AM

      Why do ancestors matter? In a BST, every node meets the requirement that child->left < node > child->right. So if you recursively verify this condition you have verified that the tree is a BST.

      This is the same solution as walking the tree in-order and dumping it to an array and then verifying the array is in sorted order, just without the array step.

      I'm honestly asking what you might see wrong with this approach, as it worked on all the test cases I gave it.

      Delete
    3. UnknownSeptember 11, 2013 at 7:30 AM

      Well heck, I googled it and yeah looks like you're right, my method will pass incorrect trees.

      However there is a much easier fix: simply retain a min/max value and pass that down the tree as you verify.

      I maintain that the solution devised above is inefficient.

      Delete
    4. AviOctober 7, 2015 at 1:40 PM

      @Unknown guy:
      The first solution is doing exactly what you are suggesting. When you traverse pre-order, you are updating the new min/max value(s) as you go down the tree.

      Delete
  3. UnknownMarch 22, 2014 at 5:22 AM

    I was asked the question and I had a slightly different solution as the first solution above, which was as follows:

    bool validate(TreeNode* root, int min, int max) {
    if (!root || (!root->right && !root->left) ) {
    return true;
    }

    if (root->left && (root->left->value > root->value || (root->left->value > max || root->left->value < min))) {
    return false;
    }
    if (root->right && (root->right->value < root->value || (root->right->value > max || root->right->value < min))) {
    return false;
    }

    return validate(root->left, min, root->value) && validate(root->right, root->value, max);
    }

    I think this recurses less number of times. However, I had forgotten to check whether left node's value is less than min, or right node's value is more than max. So, I was rejected for that.

    ReplyDelete
  4. Tushar GoelSeptember 10, 2015 at 7:13 PM

    I think another approach will be compare each node with it parent node. left node <= parent node <= right node.

    Here is recursive call:

    private int isBST(Node node) {
    if (node == null) {
    return 0;
    }

    int cmp = node.left == null ? 0 : node.left.key.compareTo(node.key);
    int cmp1 = node.right == null ? 0 : node.right.key.compareTo(node.key);
    if (cmp <= 0 && cmp1 >= 0) {
    int n1 = isBST(node.left);
    int n2 = isBST(node.right);
    if (n1 != 0 || n2 != 0) {
    return -1;
    } else {
    return 0;
    }

    } else {
    return -1;
    }
    }

    ReplyDelete
    Replies
    1. AviOctober 7, 2015 at 1:45 PM

      This comment has been removed by the author.

      Delete
    2. AviOctober 7, 2015 at 1:46 PM

      Tushar Goyal, your approach will return TRUE for certain binary tress that are not BST.
      Test Example:
      -------------------10
      -------------------/--\
      ------------------/----\
      ----------------5-----20
      ---------------/--\
      --------------/----\
      -------------2----50

      Clearly, 5<10<20 and 2<5<50, so your suggested algorithm will pass the tests even when this is not a BST

      Delete
  5. UnknownNovember 29, 2016 at 3:30 AM

    in the function(isBSTcore_solution1) of the in_order traverse the min value can be equal to the proot->nvalue and greater or less than proot->nvalue .but you checked only the greater than or less than condition.

    ReplyDelete
  6. niveJune 25, 2021 at 9:34 PM

    thanks for sharing valuable information...
    Cadd centre fee structure in coimbatore | Cadd course in coimbatore | Autocad course in coimbatore | Solidworks course in coimbatore | 3dsmax course in coimbatore | Coreldraw course in coimbatore | Electrical Cad course in coimbatore | Best cad training centre in coimbatore | Ansys training in coimbatore | Catia training in coimbatore | Civilcad training in coimbatore | Cad software training course in coimbatore | Cad Project in Coimbatore

    ReplyDelete

Subscribe to: Post Comments (Atom)