1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Binary Search Tree help C++

  1. Mar 21, 2009 #1
    1. The problem statement, all variables and given/known data
    I am working on an assignment in which I have to add a method to my BST class which checks if a binary tree object is in fact a Binary Search tree. So
    (1) A left child must be smaller than the parent
    (2) A right child must be larger than the parent
    and:
    (3) There cannot be any repeat data values

    I think my code works for the first two conditions. What it does is check the root first against its maximum (right-most leaf) and minimum (left-most leaf) values. If that's true, then the method will call itself, checking that each subtree's parent is less than the right max value and and greater than the left min value.

    However, this does not work correctly if a data value of the binary tree has been repeated.
    I am completely stumped on how to also check for this case.


    2. Relevant equations

    bool isBST() --> sets initial min and max values to start check and calls second isBST method
    bool isBST(Node<t>* r, int max, int min) --> checks to see if the < > rules have been followed

    3. The attempt at a solution
    Code (Text):

    //******************************************************************
    // Function name: isBST
    //*******************************************************************
    template <class T>
    bool BST<T> :: isBST() {
        Node<T>* seekerL = root,
               * seekerR = root;
        T minimum,
          maximum;

        if(!seekerL) { // if the tree is empty return true
            return true;
        } else { // find the left and right min and max values of the tree
            while(seekerL) {
                minimum = seekerL->key;
                seekerL = seekerL->left;
            }

            while(seekerR) {
                maximum = seekerR->key;
                seekerR = seekerR->right;
            }
        }

        // check that the tree and its subtrees follow the BST rules
        return isBST(root, minimum , maximum);
    } // end isBST

    //******************************************************************
    // Function name: isBST
    //*******************************************************************
    template <class T>
    bool BST<T> :: isBST(Node<T>* r, T min, T max) {
        Node<T> *parent = r;

        // if the parent has no children a leaf node has been reached
        if(!parent) {
            return true;
        }

        // if parent does not fall inbetween max or min return false
        if (parent->key < min || parent->key > max) {
            return false;
        }

        // else keep checking each subtree until rule is broken or tree is BST
        return (isBST(parent->left, min, parent->key) && isBST(parent->right, parent->key+1, max));
    } // end isBST
     
    Any help would be greatly appreciated. :)

    Edit: Oh and the test data/key I am using is a Binary Tree of integers.
     
    Last edited: Mar 21, 2009
  2. jcsd
  3. Mar 22, 2009 #2
    Never mind. I think I may have figured out another way to check my tree.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Binary Search Tree help C++
  1. Binary Search tree (Replies: 5)

Loading...