Software & Finance - Monthly Magazine Online

Volume 2 - Issue 9

September 2012

Technology: Binary Search Tree Validation


The complete C++ source code for validating the binary search tree is given on this page.

 

All the nodes to left are less than the current node value and all nodes to the right are greater than the current node value. It would be true for each and every node in the binary search tree.

 

I have explained two algorithms for checking the validity of a binary search tree. Both methods are using recursive.

 

 

Source Code

 

// BST.cpp : Defines the entry point for the console application.

//

 

#include "stdafx.h"

#include "windows.h"

#include <iostream>

 

 

typedef struct _BSTNode

{

    struct _BSTNode *left;

    struct _BSTNode *right;

    int data;

} BSTNode;

 

BSTNode* NewNode(int data)

{

    BSTNode *pNewNode = new BSTNode();

    pNewNode->left = pNewNode->right = NULL;

    pNewNode->data = data;

    return pNewNode;

}

 

void PrintPostOrder(BSTNode *node)

{

    if(node == NULL)

        return;

    PrintPostOrder(node->left);

    PrintPostOrder(node->right);

 

    std::cout << node->data << " ";

}

 

static BSTNode *root = NULL;

 

int MaxDepth(BSTNode *node)

{

    if(node == NULL)

        return 0;

    int ldepth = MaxDepth(node->left);

    int rdepth = MaxDepth(node->right);

 

    int max = (ldepth > rdepth) ? ldepth : rdepth;

 

    return (max + 1);

}

 

void PrintTree(BSTNode *node)

{

    if(node == NULL)

        return;

    PrintTree(node->left);

   

    //gotoxy(node->xpos, node->ypos);

 

    std::cout << node->data << " ";

 

    PrintTree(node->right);

}

 

 

BSTNode* Insert(BSTNode* node, int data)

{

    if(node == NULL)

        return NewNode(data);

 

    if(data <= node->data)

    {

        if(node->left == NULL)

            node->left = NewNode(data);

        else

            node->left = Insert(node->left, data);

    }

    else

    {

        if(node->right == NULL)

            node->right = NewNode(data);

        else

            node->right = Insert(node->right, data);

    }

    return node;

}

 

 

BSTNode* Insert2(BSTNode* node, int data)

{

    if(node == NULL)

        return NewNode(data);

 

    if(data <= node->data)

    {

        if(node->left == NULL)

        {

            node->left = NewNode(data);

        }

        else

            if(node->right == NULL)

            {

                // Rearrange

                 int temp = node->data;

                 node->data = node->left->data;

                 node->right = node->left; // reuse valid left pointer

                 node->right->data = temp;

                 node->left = NewNode(data);

            }

            else

            {

                node->left = Insert2(node->left, data);

            }

    }

    else

    {

        if(node->left == NULL) // left must be filled in first

        {

            // swap the values

            int temp = node->data;

            node->data = data;

            data = temp;

            // insert now

            node->left = NewNode(data);

        }

        else

        {

            if(node->right == NULL)

                node->right = NewNode(data);

            else

                node->right = Insert2(node->right, data);

        }

    }

    return node;

}

 

int maxValueOfBST(BSTNode *node, int max = INT_MIN)

{

    if(node == NULL)

        return max;

 

    if(node->data > max)

        max = node->data;

    max = maxValueOfBST(node->left, max);

    max = maxValueOfBST(node->right, max);

    return max;

}

 

int minValueOfBST(BSTNode *node, int min = INT_MAX)

{

    if(node == NULL)

        return min;

 

    if(node->data > min)

        min = node->data;

    min = minValueOfBST(node->left, min);

    min = minValueOfBST(node->right, min);

    return min;

}

 

bool IsBinarySearchTree(BSTNode *node)

{

  if (node == NULL)

  {

    return(true);

  }

  else {

      if(node->left != NULL && node->data <= maxValueOfBST(node->left))

      {

          return false;

      }

 

      if(node->right != NULL && node->data >= minValueOfBST(node->right))

      {         

          return false;

      }

 

    if(IsBinarySearchTree(node->left) == false ||

        IsBinarySearchTree(node->right) == false)

    {

        return(false);

    }

  }

  return true;

}

 

int IsBinarySearchTree(BSTNode * root, BSTNode **min, BSTNode **max)

{

    BSTNode *minLeft, *minRight, *maxLeft, *maxRight;

    if(root == NULL)

    {

        *min = NULL; *max = NULL; return(1);

    }

 

    if(!IsBinarySearchTree(root->left, &minLeft, &maxLeft))

        return(0);

    if(!IsBinarySearchTree(root->right, &minRight, &maxRight))

        return(0);

 

    if(maxLeft != NULL && root->data < maxLeft->data)

        return(0);

 

    if(minRight != NULL && root->data > minRight->data)

        return(0);

 

    if(minLeft != NULL) *min = minLeft; else *min = root;

 

    if(maxRight != NULL) *max = maxRight; else *max = root;

 

   

    std::cout << "Node : " << root->data << " Min: " << (*min)->data

        << " Max: " << (*max)->data << "\n";

 

    return(1);

}

 

int _tmain(int argc, _TCHAR* argv[])

{

    // 1st level

    root = Insert(NULL, 60);

   

    // 2nd level

    Insert(root, 40);

    Insert(root, 80);

 

    // 3rd level

    Insert(root, 30);

    Insert(root, 50);

    Insert(root, 70);

    Insert(root, 90);

 

    //Uncomment the following line to NOT make it a Binary Tree

    //Insert(root->left->left, 100);

 

    PrintTree(root);

    std::cout << "\n";

    PrintPostOrder(root);

 

    std::cout << "\n";

    std::cout << "Depth: " << MaxDepth(root);

    std::cout << "\n\n";

 

    BSTNode *l, *r;

 

    // Method 1

    if(IsBinarySearchTree(root, &l, &r) == true)

        std::cout << "\nMethod1:  is a BST\n";

    else

        std::cout << "\nMethod1:  is NOT a BST\n";

 

    // Method 2

    if(IsBinarySearchTree(root) == true)

        std::cout << "\nMethod2:  is a BST\n";

    else

        std::cout << "\nMethod2:  is NOT a BST\n";

 

      return 0;

}

 

 

 

 

30 40 50 60 70 80 90

30 50 40 70 90 80 60

Depth: 3

 

Node : 30 Min: 30 Max: 30

Node : 50 Min: 50 Max: 50

Node : 40 Min: 30 Max: 50

Node : 70 Min: 70 Max: 70

Node : 90 Min: 90 Max: 90

Node : 80 Min: 70 Max: 90

Node : 60 Min: 30 Max: 90

 

Method1:  is a BST

 

Method2:  is a BST

Press any key to continue . . .