Validate matrix valid BST

Question

Given a binary tree represented as a matrix, write a function to determine if it is a valid binary search tree (BST). A valid BST must satisfy the property that for any given node, all values in its left subtree are less than the node's value, and all values in its right subtree are greater. The function should return a boolean value indicating whether the matrix represents a valid BST.

Codemia · Accepted Answer

To determine if a matrix representation of a binary tree is a valid Binary Search Tree (BST), we need to ensure that for every node, all values in the left subtree are less than the node's value and all values in the right subtree are greater. The two-pointer technique is not applicable here. Instead, we can use a depth-first search (DFS) approach with boundaries for the node values. Each node in the matrix can be accessed using its row and column indices, and we will check if the current node's value is within the specified valid range derived from its parent nodes.

1. Define a recursive function `is_valid_bst` that takes the current node's value, the lower limit, and the upper limit as parameters.  
2. For the root of the matrix, initialize the limits as negative infinity and positive infinity.  
3. If the current node is `None`, return `True` (base case).  
4. Check if the current node's value is within the limits. If it is not, return `False`.  
5. Recursively check the left child with updated upper limit (current node's value) and the right child with updated lower limit (current node's value).  
6. Call the `is_valid_bst` on the root of the matrix to start the validation process.  
Example: For a matrix like [[2], [1, 3]], the root is 2, left child is 1 (valid), and right child is 3 (valid), hence it’s a valid BST.

```python
def is_valid_bst_matrix(matrix):
    if not matrix:
        return True

def is_valid_bst(node_index, lower=float('-inf'), upper=float('inf')):
        if node_index is None:
            return True
        row, col = node_index
        node_value = matrix[row][col]

if not (lower < node_value < upper):
            return False

left_child_index = (row + 1, col)  # Assuming left child is directly below
        right_child_index = (row + 1, col + 1)  # Assuming right child is to the right

return (is_valid_bst(left_child_index, lower, node_value) and
                is_valid_bst(right_child_index, node_value, upper))

return is_valid_bst((0, 0))  # Start from the root of the matrix
```

The time complexity of this approach is O(N), where N is the number of nodes in the matrix. Each node is visited once during the DFS traversal. The space complexity is O(H), where H is the height of the tree due to the recursion stack. In the worst case, if the tree is skewed, H could be as large as N.

1. **Empty Matrix**: An empty matrix should return `True` as it represents a valid BST (base case).  
2. **Single Node**: A matrix with a single node should also return `True`, as there are no children to violate the BST properties.  
3. **Invalid BST Structure**: A matrix like [[5], [6, 4]] should return `False` since the left child (4) is greater than the root (5).  
4. **Matrix with Duplicates**: If the matrix contains duplicate values, it should return `False`, as BSTs do not allow duplicates.

Validate matrix valid BST

Citadel

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Citadel Machine Learning Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string