Share

## Question: TestDome - BinarySearchTree

15 February 2018

Views: 27

`/*   Question: TestDome - BinarySearchTree   Solution by Arash Partow 2014   Write a function that checks if a given binary tree is a valid   binary search tree. A binary search tree (BST) is a binary tree   where the value of each node is larger or equal to the values in   all the nodes in that node's left subtree and is smaller than the   values in all the nodes in that node's right subtree.   For example, for the following tree:   n1 (Value: 1, Left: null, Right: null)   n2 (Value: 2, Left: n1, Right: n3)   n3 (Value: 3, Left: null, Right: null)   Call to isValidBST(n2) should return true since a tree with root at   n2 is a valid binary search tree.   Explanation: Subtrees rooted at nodes n1 and n3 are valid binary   search trees as they have no children. A tree rooted at node n2 is   a valid binary search tree since its value (2) is larger or equal   to the largest value in its left subtree (1, rooted at n1) and is   smaller than the smallest value in its right subtree (3 rooted at   n3).*/#include <stdexcept>#include <string>#include <iostream>#include class Node{public:   Node(int value, Node* left, Node* right)   {      this->value = value;      this->left = left;      this->right = right;   }   int getValue() const   {      return value;   }   Node* getLeft() const   {      return left;   }   Node* getRight() const   {      return right;   }private:   int value;   Node* left;   Node* right;};class BinarySearchTree{public:   static bool isValidBST(const Node& root)   {      if (!isValidBST_left_impl(root.getLeft(),root.getValue()))         return false;      else if (!isValidBST_right_impl(root.getRight(),root.getValue()))         return false;      else if (root.getLeft () && (root.getLeft()->getValue() >= root.getValue()))         return false;      else if (root.getRight() && (root.getRight()->getValue() < root.getValue()))         return false;      return true;   }private:   static bool isValidBST_right_impl(const Node* root, int parent_v)   {      if (root == 0)         return true;      if (!branch_leftright(root))         return false;      if (root->getLeft() && root->getRight())         return parent_v < std::min(root->getLeft()->getValue(), root->getRight()->getValue());      else if (root->getLeft())         return parent_v < root->getLeft()->getValue();      else if (root->getRight())         return parent_v < root->getRight()->getValue();      return parent_v < root->getValue();   }   static bool isValidBST_left_impl(const Node* root, int parent_v)   {      if (root == 0)         return true;      if (!branch_leftright(root))         return false;      if (root->getLeft() && root->getRight())         return parent_v >= std::max(root->getLeft()->getValue(), root->getRight()->getValue());      else if (root->getLeft())         return parent_v >= root->getLeft()->getValue();      else if (root->getRight())         return parent_v >= root->getRight()->getValue();      return parent_v >= root->getValue();   }   static bool branch_leftright(const Node* root)   {      if (!isValidBST_left_impl(root->getLeft(),root->getValue()))         return false;      else if (!isValidBST_right_impl(root->getRight(),root->getValue()))         return false;      return true;   }};#ifndef RunTestsint main(int argc, const char* argv[]){   Node n1(1, NULL, NULL);   Node n3(3, NULL, NULL);   Node n2(2, &n1, &n3);   std::cout  BinarySearchTree::isValidBST(n2);   return 0;}#endif`