Validating A Binary Search Tree

Validating A Binary Search Tree

The logic behind validating a binary binary search tree is :
1. The in-order traversal of a binary search tree is always in the increasing order.


C++ : Validating a binary search tree. Implemented in C++11

#include<iostream>
#include<vector>
using namespace std;

class Node {

    public:
    int data;
    Node * left;
    Node * right;
    Node(int x) : data(x), left(NULL), right(NULL)
    {}
};

class Tree {

    public:

    vector<int> order;

    /* The in-order traversal of a valid binary search tree is always in increasing order (sorted) */
    void InOrder(Node * node) {

        if (node != NULL) {
            InOrder(node->left);
            order.push_back(node->data);
            InOrder(node->right);
        }
    }

    bool IsValidBST(Node * node) {

        InOrder(node);
        for (int i=1; i < order.size(); i++) {
            if (order[i-1] > order[i])
                return false;
        }
        return true;
    }
};

int main() {

    /*   2 
        / \
       1   3  */

    Node * root1 = new Node(2);
    root1->left = new Node(1);
    root1->right = new Node(3);

    Tree t;
    if (t.IsValidBST(root1)) {
        cout << "Tree is a valid binary search tree" << endl;
    } else {
        cout << "Tree is a not a valid binary search tree" << endl;
    }

    /*   5
        / \
       1   6  
          / \
         7   8  */
    Node * root2 = new Node(5);
    root2->left = new Node(1);
    root2->right = new Node(6);
    root2->right->left = new Node(7);
    root2->right->right = new Node(8);

    if (t.IsValidBST(root2)) {
        cout << "Tree is a valid binary search tree" << endl;
    } else {
        cout << "Tree is a not a valid binary search tree" << endl;
    }

    /*   1 
        / 
       1   */
    Node * root3 = new Node(1);
    root3->left = new Node(1);

    if (t.IsValidBST(root3)) {
        cout << "Tree is a valid binary search tree" << endl;
    } else {
        cout << "Tree is a not a valid binary search tree" << endl;
    }

    /*   10
        /  \
       5    15 
           /  \
          6   20 */

    Node * root4 = new Node(10);
    root4->left = new Node(5);
    root4->right = new Node(15);
    root4->right->left = new Node(6);
    root4->right->right = new Node(20);

    if (t.IsValidBST(root4)) {
        cout << "Tree is a valid binary search tree" << endl;
    } else {
        cout << "Tree is a not a valid binary search tree" << endl;
    }

    return 0;
}

Output of validating a binary search tree implemented in C++11

Tree is a valid binary search tree
Tree is a not a valid binary search tree
Tree is a not a valid binary search tree
Tree is a not a valid binary search tree

Copyright © 2020, Algotree.org.
All rights reserved.