Validate Search Binary Tree [closed]

Question

Closed. This question is off-topic. It is not currently accepting answers.

Code not implemented or not working as intended: Code Review is a community where programmers peer-review your working code to address issues such as security, maintainability, performance, and scalability. We require that the code be working correctly, to the best of the author's knowledge, before proceeding with a review.

Closed 5 years ago.

Improve this question

I was looking to this exercise: Is Valid Binary Search Tree

I tried to do the exercise by myself without looking to the solution and my code is "much simpler" than the code I found at the previous link. Is there anyone that can review this code or provide me some test cases for this problem? Generating test cases is way more time consuming than coding.

    /*
   Question: TestDome - BinarySearchTree
   Solution by Antonio Di Bacco 2020

   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 <algorithm>

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 (root.getRight() == nullptr) {
            if (root.getLeft() == nullptr) {
                return true;
            }
            else {
                if (root.getLeft()->getValue() < root.getValue())
                    return isValidBST(*(root.getLeft()));
                else
                    return false;
            }
        }
        else {
            if (root.getLeft() == nullptr) {
                if (root.getRight()->getValue() > root.getValue())
                    return isValidBST(*(root.getRight()));
                else
                    return false;
            }
            else {
                if ((root.getRight()->getValue() > root.getValue()) && (root.getLeft()->getValue() < root.getValue()))
                    return isValidBST(*(root.getLeft())) && isValidBST(*(root.getRight()));
                else
                    return false;
            }
        }

    }

private:

 

};


#ifndef RunTests
int main(int argc, const char* argv[])
{
    Node n1(1, NULL, NULL);
    Node n3(3, NULL, NULL);
    Node N(2, &n1, &n3);

    std::cout << BinarySearchTree::isValidBST(N) << std::endl;

    Node m1(1, NULL, NULL);
    Node m3(3, NULL, NULL);
    Node M(2, &m3, &m1);

    std::cout << BinarySearchTree::isValidBST(M) << std::endl;

    Node p4(5, NULL, NULL);
    Node p1(1, NULL, NULL);
    Node p3(3, &p4, NULL);
    Node P(2, &p1, &p3);

    std::cout << BinarySearchTree::isValidBST(P) << std::endl;

    return 0;
}
#endif

If you replace the 5 in your third test with -5, you incorrectly report the tree to be a valid BST. — Kelly Bundy
– Kelly Bundy, Commented Sep 27, 2020 at 15:46
The solution is not correct. It is not enough to test the root agains its immediate children. In a valid BST all the values in the entire left subtree must be less than the root value. Consider a tree (3, (2, (1), (5)), (...)). It is not valid (5 in the left subtree is greater than 3 at the root). — vnp
– vnp, Commented Sep 27, 2020 at 16:16

Kelly Bundy · Accepted Answer · 2020-09-27 20:45:23Z

To validate a BST tree you need to validate a sub tree is between two values.

Remember that all nodes to the left must be less than the current node and everything to the right is larger. So after a left then a right you have a set of bounds (min and max).

So when you are doing the validation I would expect to see you pass the bounds as you move down the sub-tree (now for the root you pass -MinInt +MaxInt as the bounds).

bool isValid(Node* root)
{
    return isBound(root,
                   std::numeric_limits<int>::min,
                   std::numeric_limits<int>::max);
}
bool isBound(Node* node, int min, int max)
{
    if (node == nullptr) {
        return true;
    }
    if (node->value < min || node->value > max) {
        return false;
    }
    return isBound(node->left, min, node->value)
        && isBound(node->right, node->value, max);
}

Stack Exchange Network

Validate Search Binary Tree [closed]

1 Answer 1

Hot Network Questions

Validate Search Binary Tree [closed]

1 Answer 1

Related

Hot Network Questions