Month: February 2020

Check if a binary tree is a valid BST

Definition for a binary tree node:

struct TreeNode {
   int value;
   TreeNode *left;
   TreeNode *right;
   TreeNode( int x ) : value( x ), left( nullptr ), right( nullptr ) {}
}

A straightforward but incorrect solution:

bool validateBST( TreeNode *root ) {
   if( root == nullptr ) {
     return true;
   }
   
   if( root->left != nullptr && root->left->value > root->value ) {
     return false;
   }
   
   if( root->right != nullptr && root->right->value < root->value ) {
     return false;
   }
   
   if( !validateBST( root->left ) || !validateBST( root->right ) ) {
     return false;
   }
   
   return true;
}

Test it.

#include <iostream>

int main (int argc, char** argv)
{
  {
    TreeNode *root    = new TreeNode( 3 ); 
    root->left        = new TreeNode( 2 ); 
    root->right       = new TreeNode( 5 ); 
    root->left->left  = new TreeNode( 1 ); 
    root->left->right = new TreeNode( 4 ); 

    std::cout<< validateBST( root ) << std::endl;  // Expect 0
  }
  
  {
    TreeNode *root    = new TreeNode( 4 ); 
    root->left        = new TreeNode( 2 ); 
    root->right       = new TreeNode( 5 ); 
    root->left->left  = new TreeNode( 1 ); 
    root->left->right = new TreeNode( 3 ); 

    std::cout<< validateBST( root ) << std::endl;  // Expect 1
  }

  return 0;
}

Build and run it.

g++ main.cpp --std=c++14
./a.out
1
1

A correct solution:

#include <climits>

bool isValidBST( TreeNode *root, int min, int max ) {
  if( root == nullptr ) {
    return true;
  }
  
  if( root->value < min || root->value > max ) {
    return false;
  }
  
  return isValidBST( root->left, min, root->value - 1 ) && 
         isValidBST( root->right, root->value + 1, max );
}

bool validateBST( TreeNode *root ) {
  return isValidBST( root, INT_MIN, INT_MAX );
}

Use the same “main” to test it.

g++ main.cpp --std=c++14
./a.out
0
1

A better solution:

bool isValidBST( TreeNode *root, TreeNode *left, TreeNode *right ) {
  if( root == nullptr ) {
      return true;
  }

  if( left != nullptr && left->value >= root->value ) {
      return false;
  }

  if( right != nullptr && right->value <= root->value ) {
      return false;
  }

  return isValidBST( root->left, left, root ) && 
         isValidBST( root->right, root, right );
}

bool validateBST( TreeNode *root ) {
  return isValidBST( root, nullptr, nullptr );
}