We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Data Structures
  3. Trees
  4. Is This a Binary Search Tree?
  5. Discussions

Is This a Binary Search Tree?

  • gschoen
     + 1 comment

    I did a similar thing (except that the list was in descending order). My recursive algorithm had a flaw that appeared to be too difficult to waste time fixing.

    Note that I am more used to C so I didn't bother with the C++ libraries.

        struct List {
        int data;
        List *next;
    };

    List *makeDescendingList(Node *head, List *list) {
        List *newListNode;
        if (head == NULL) {
            return list;
        } else {
            list = makeDescendingList(head->left, list);
            newListNode = new(List);
            newListNode->data = head->data;
            newListNode->next = list;
            return makeDescendingList(head->right, newListNode);
        } 
    }

    bool isDescendingList (List *list) {
        while (list != NULL) {
            if (list->next != NULL && list->data <= list->next->data) {
                return false;
            }
            list = list->next;
        }
        return true;
    }
    
	bool checkBST(Node* root) {
		return isDescendingList(makeDescendingList(root, NULL));
	}