Algotree > Algorithms > Tree & Graph Traversal > Binary Search Tree > Validating A Binary Search Tree (BST)

Validating A Binary Search Tree (BST)

Validate_BST The logic behind validating a BST is :

The in-order traversal of a binary search tree will always have the nodes in increasing order. Thus, given a tree we traverse it in an in-order manner and look at the sequence of nodes. If the nodes are in increasing order then the traversed tree is a valid Binary Search Tree.

Example : Consider a valid and an invalid BST as shown.

Inorder traversal of valid binary search tree : 3 5 6 7 10. ( The numbers are in ascending order )
Inorder traversal of an invalid binary search tree : 3 5 7 6 10. ( The numbers are not in ascending order )

Time Complexity of validating a BST with N nodes : O ( N ), as the in-order traversal visits each node of the binary search tree once, the time complexity is O ( N ).

C++ : Program for validating a BST

#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)
    {}
    Node(int x, Node* left_node, Node* right_node) : data(x), left(left_node), right(right_node)
    {}
};

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() {

    /*   5
        / \
       1   7  
          / \
         6   8  */
    Node node6(6), node8(8), node1(1);
    Node node7(6, &node6, &node8);
    Node root_node5(5, &node1, &node6);

    Tree t;

    /*  3
       / 
      4   */
    Node node4(4);
    Node root_node3(3, &node4, nullptr);

    /*   10
        /  \
       2    15 
           /  \
          9   20 */

    Node node9(9), node20(20), node2(2);
    Node node15(15, &node9, &node20);
    Node root_node10(10, &node2, &node15);

    vector<Node> roots = { root_node5, root_node3, root_node10 };

    for (auto root : roots) {
        if (t.IsValidBST(&root)) {
            cout << "Tree with root node (" << root.data << ") is a valid binary search tree" << endl;
        } else {
            cout << "Tree with root node (" << root.data << ") is not a valid binary search tree" << endl;
        }
    }
    return 0;
}

Output

Tree with root node (5) is a valid binary search tree
Tree with root node (3) is not a valid binary search tree
Tree with root node (10) is not a valid binary search tree