Sunday, 10 June 2012

Check if tree is a BST O(n) code Common Interview Question

Check if tree is a Binary Search Tree or not 

Most Common Interview Question

Problem Statement

Write a program to check if a tree is a Binary Search Tree or not.


While doing in-order traversal, keep track of previous node in a static variable and compare its data with root's (next) data. Plus also check if left subtree and right subtree also follow binary search tree property.

If you have a different approach in mind, please share it in comments section for our readers.


int isBST(node *root) {

    static int node *prev_node = NULL;
    if(root == NULL) return 1;
        return 0;
    if(prev_node != NULL && root->data <= prev_node->data)
        return 0;
    prev_node = root;
        return 0;
    return 1;       

Time Complexity

O(n) since we visit each node only once.

If you find this blog somewhat helpful, please give a +1.

No comments:

Post a Comment