Taro Logo

Validate Binary Search Tree

Medium
Amazon logo
Amazon
1 view
Topics:
TreesRecursion

Given the root of a binary tree, determine if it is a valid binary search tree (BST). A valid BST is defined as follows:

  1. The left subtree of a node contains only nodes with keys less than the node's key.
  2. The right subtree of a node contains only nodes with keys greater than the node's key.
  3. Both the left and right subtrees must also be binary search trees.

For example, consider the following binary tree:

    5
   / \
  1   4
     / \
    3   6

Is this a valid BST? The answer is false, because the node with value 4 is the right child of the node with value 5, but 4 < 5. The node with value 3 is the left child of the node with value 4, but 3 < 4. The node with value 6 is the right child of the node with value 4, and 6 > 4. Also, the subtrees rooted at 1, 3 and 6 are valid BSTs.

Another example:

    2
   / \
  1   3

This is a valid BST. The node with value 1 is the left child of the node with value 2, and 1 < 2. The node with value 3 is the right child of the node with value 2, and 3 > 2. Also, the subtrees rooted at 1 and 3 are valid BSTs.

Write an efficient algorithm to determine if a given binary tree is a valid BST.

Solution


Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. What is the range of values for the nodes in the binary tree? Should I expect negative numbers, zeros, or any upper limit?
  2. Are duplicate values allowed in the binary search tree? If so, how should they be handled to maintain the BST property (e.g., should they go to the left or right subtree)?
  3. Can the tree be empty (i.e., root is null)? If so, what should I return?
  4. By 'keys', do you mean the actual node values, or do the nodes have a separate 'key' property?
  5. Is it guaranteed that the input is actually a binary tree, or might I encounter a more general graph structure with potential cycles?

Brute Force Solution

Approach

To check if a tree is a valid Binary Search Tree (BST) using a brute force method, we essentially want to confirm that every node follows the BST property: smaller values on the left and larger values on the right. This involves exhaustively examining each node in relation to all other nodes within its potential range.

Here's how the algorithm would work step-by-step:

  1. Begin by checking the root node. For it to be valid, all nodes in its left side must have values smaller than the root, and all nodes on the right side must have values larger than the root.
  2. Now, move to the left 'branch' (or 'subtree') of the root. We need to independently verify if this branch itself satisfies the BST property. That is, every node to the left of any particular node in this branch should be smaller than it, and every node to the right should be larger.
  3. However, there is a key restriction. Because this entire left branch descends from the root, all nodes in the left branch must still be smaller than the root's value. This means, while checking the left branch, we always compare each node with the root's value, too.
  4. Next, we need to do the same for the right branch of the root. This right branch must also satisfy the BST property internally, but with a crucial addition: every node in this branch must also be larger than the root node's value.
  5. Recursively repeat these checks for every node in the tree. In simpler terms, for each node we visit, check if its children fit the BST property, and if that child itself is the root of its own subtree, repeat the check within that subtree too.
  6. If, during any of these checks, we find a node that violates the BST property (e.g., a node in the left branch is bigger than the root, or a node in the right branch is smaller), then the whole tree is not a valid BST.
  7. Only if all nodes pass these checks and no violations are found is the tree considered a valid Binary Search Tree.

Code Implementation

def is_valid_bst_brute_force(root):
    def is_valid_subtree(node, less_than_value, greater_than_value):
        if node is None:
            return True

        # Check if the current node violates the BST property
        if not (less_than_value is None or node.val < less_than_value) or \
           not (greater_than_value is None or node.val > greater_than_value):
            return False

        # Recursively check the left and right subtrees
        # Ensure the left subtree is less than the current node
        if not is_valid_subtree(node.left, node.val, greater_than_value):
            return False

        # Ensure the right subtree is greater than the current node
        if not is_valid_subtree(node.right, less_than_value, node.val):
            return False

        return True

    # Begin the validation from the root node
    return is_valid_subtree(root, None, None)

Big(O) Analysis

Time Complexity
O(n²)The brute force approach checks each node against all other nodes in its potential range to validate the BST property. In the worst case, for each of the n nodes, we might potentially need to traverse a significant portion of the tree to check if the BST properties are maintained, especially considering nodes that might require comparisons against all ancestors. This leads to approximately n operations for each of the n nodes. Therefore, the time complexity is O(n²).
Space Complexity
O(H)The algorithm uses a recursive approach. In the worst-case scenario, where the tree is skewed (e.g., a linked list), the recursion depth can be equal to the height (H) of the tree, leading to H function calls on the call stack. Each function call consumes some memory for local variables and return addresses. Therefore, the auxiliary space complexity is proportional to the height of the tree. In the best and average case for balanced trees, H would be log(N), where N is the number of nodes. However, the worst case is still O(H).

Optimal Solution

Approach

To check if a tree is a valid Binary Search Tree, we use the properties that each node's value must fall within a specific range. This approach uses the tree's structure to efficiently confirm that these properties hold true for all nodes, without explicitly checking every possible relationship.

Here's how the algorithm would work step-by-step:

  1. Start at the very top node of the tree.
  2. For each node, set a minimum and maximum allowed value. Initially, these can be considered unlimited in both directions (like negative infinity and positive infinity).
  3. Go down the left path. As you go left, the maximum allowed value for that node is the value of the node you just came from.
  4. Go down the right path. As you go right, the minimum allowed value for that node is the value of the node you just came from.
  5. At each node, check that its value is within the allowed range (between the minimum and maximum values you set as you moved down the tree).
  6. If any node's value is outside the allowed range, the tree is invalid. If every node passes this check, the tree is valid.

Code Implementation

def is_valid_bst(root):
    def validate_node(node, minimum_value, maximum_value):
        if not node:
            return True

        # Check current node's value is within bounds
        if not (minimum_value < node.val < maximum_value):
            return False

        # Ensure left subtree is a valid BST
        if not validate_node(node.left, minimum_value, node.val):
            return False

        # Ensure right subtree is a valid BST
        if not validate_node(node.right, node.val, maximum_value):
            return False

        return True

    # Start validation with unbounded min/max values
    return validate_node(root, float('-inf'), float('inf'))

Big(O) Analysis

Time Complexity
O(n)The algorithm traverses the binary tree, visiting each node exactly once. For each node, it performs a constant amount of work: comparing the node's value against the provided minimum and maximum bounds. The number of nodes is represented by n, where n is the total number of nodes in the tree. Therefore, the time complexity is directly proportional to the number of nodes, resulting in O(n).
Space Complexity
O(H)The space complexity is determined by the recursion stack used during the depth-first traversal of the binary search tree. In the worst case, where the tree is skewed (essentially a linked list), the recursion depth can reach N, where N is the number of nodes in the tree. In the best and average cases, where the tree is balanced, the recursion depth is logarithmic, approximately log(N), which we can denote as H, the height of the tree. Thus, the auxiliary space used by the recursion stack is O(H).

Edge Cases

CaseHow to Handle
Null root nodeAn empty tree is considered a valid BST, so return true.
Single node treeA tree with only a root node is a valid BST, so return true.
Tree with duplicate values (adjacent to each other)The valid BST definition requires strict inequality; the solution should check that the left subtree is strictly less than the node and the right subtree is strictly greater than the node.
Tree with duplicate values (non-adjacent, violating BST property)The recursive calls will eventually find the violation where a node in the left or right subtree has an invalid value.
Tree with negative valuesThe comparison should work correctly with negative values as integers are comparable in a standard way.
Very large tree (potential stack overflow with recursion)Iterative solutions using a stack may be preferred to avoid stack overflow errors for very large trees, limiting recursion depth.
Tree with Integer.MAX_VALUE and Integer.MIN_VALUEEnsure initial min/max bounds are set such that comparisons with these extreme values work correctly to avoid overflow problems.
Skewed Tree (all nodes on one side)The solution should still correctly validate a skewed tree because it checks all nodes against the allowed min/max range within the entire tree, though performance might degrade.