algoadvance

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

• The left subtree of a node contains only nodes with values less than the node’s value.
• The right subtree of a node contains only nodes with values greater than the node’s value.
• Both the left and right subtrees must also be binary search trees.

Example 1:

Input: root = [2,1,3]
Output: true

Example 2:

Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.

Clarifying Questions

1. Can the tree be empty? If yes, should we consider it as a valid BST?
2. Are there any constraints on the values stored in the tree nodes?
3. Is the tree guaranteed to be a binary tree?

Strategy

To validate whether a binary tree is a binary search tree, we can use an in-order traversal. The idea is that for a binary search tree, an in-order traversal should yield values in a strictly increasing order.

Alternatively, we can use a recursive function to ensure that each node meets the BST properties by enclosing the valid range of values for each node based on its position in the tree.

• We will implement the solution using both strategies:
  1. In-order Traversal.
  2. Recursive Range Check.

Code

Strategy 1: In-Order Traversal

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def isValidBST(root):
    def inorder(node, arr):
        if not node:
            return
        inorder(node.left, arr)
        arr.append(node.val)
        inorder(node.right, arr)
    
    values = []
    inorder(root, values)
    
    for i in range(1, len(values)):
        if values[i] <= values[i - 1]:
            return false
    return true

Strategy 2: Recursive Range Check

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def isValidBST(root):
    def validate(node, low=float('-inf'), high=float('inf')):
        if not node:
            return True
        if not (low < node.val < high):
            return False
        return (validate(node.left, low, node.val) and
                validate(node.right, node.val, high))
    
    return validate(root)

Time Complexity

In-Order Traversal

• Time Complexity: (O(n)) because each node is visited exactly once during the in-order traversal.
• Space Complexity: (O(n)) for storing the values of the nodes in the array, plus the space complexity of the recursive stack, which is (O(h)), where (h) is the height of the tree.

Recursive Range Check

• Time Complexity: (O(n)) because each node is visited exactly once.
• Space Complexity: (O(h)), where (h) is the height of the tree, due to the recursive stack space required.

Both methods efficiently determine whether the binary tree is a valid BST, and each has its own advantages in terms of implementation simplicity and space efficiency.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?