Validate Binary Search Tree

 

  1. Clarify the problem:

    • The problem requires us to validate whether a given binary tree is a valid binary search tree (BST).
    • A binary search tree is a binary tree in which the left subtree of a node contains only values less than the node's value, and the right subtree contains only values greater than the node's value.
    • We need to implement a function that takes in the root of a binary tree and returns a boolean value indicating whether the tree is a valid BST.

  2. Analyze the problem:

    • Input: Root of a binary tree.
    • Output: Boolean value indicating whether the tree is a valid BST.
    • Constraints:
      • The binary tree can have up to 10^4 nodes.
      • Node values can be any valid integer value.

  3. Design an algorithm:

    • We can solve this problem using an in-order traversal of the binary tree.
    • In a valid BST, performing an in-order traversal should yield a sorted list of values.
    • We can define a recursive function to perform the in-order traversal.
    • The function will take the current node as input and return a list of values obtained from the traversal.
    • Inside the function, we first check if the current node is None. If so, we return an empty list.
    • We recursively call the function on the left subtree and concatenate the result with the current node's value and the result from the recursive call on the right subtree.
    • Finally, we iterate over the resulting list of values and check if they are in strictly increasing order. If not, we return False. Otherwise, we return True.

  4. Explain your approach:

    • We will implement an in-order traversal algorithm to validate whether a binary tree is a valid BST.
    • First, we define a recursive function inorder that takes the current node as input and returns a list of values obtained from the in-order traversal.
    • Inside the function, we check if the current node is None. If so, we return an empty list.
    • We recursively call the inorder function on the left subtree and concatenate the result with the current node's value and the result from the recursive call on the right subtree.
    • After defining the inorder function, we initialize a variable values with the result of calling the inorder function on the root of the binary tree.
    • Next, we iterate over the values list and check if each value is strictly less than the next value. If not, we return False.
    • Finally, if all the values are in strictly increasing order, we return True.

  5. Write clean and readable code:

    python
  6. class Solution:
    def isValidBST(self, root):
        def inorder(node):
            if node is None:
                return []

            return inorder(node.left) + [node.val] + inorder(node.right)

        values = inorder(root)

        for i in range(1, len(values)):
            if values[i] <= values[i - 1]:
                return False

        return True

solution = Solution()
# Test case 1: Valid BST
#       5
#      / \
#     3   7
#    / \
#   1   4
root1 = TreeNode(5)
root1.left = TreeNode(3)
root1.right = TreeNode(7)
root1.left.left = TreeNode(1)
root1.left.right = TreeNode(4)
print(solution.isValidBST(root1))  # Output: True

# Test case 2: Invalid BST
#       5
#      / \
#     3   7
#    / \
#   1   6
root2 = TreeNode(5)
root2.left = TreeNode(3)
root2.right = TreeNode(7)
root2.left.left = TreeNode(1)
root2.left.right = TreeNode(6)
print(solution.isValidBST(root2))  # Output: False

  7. Test your code:

    • We test the code with two cases:
      1. Valid BST: The tree is a valid binary search tree.
      2. Invalid BST: The tree is not a valid binary search tree.
    • We chose these test cases to cover both scenarios and ensure the code handles both valid and invalid BSTs.

  8. Optimize if necessary:

    • The provided solution uses an in-order traversal to validate the BST.
    • The time complexity of the solution is O(N) as we need to visit each node once.
    • The space complexity is O(N) in the worst case due to the recursive calls and the list of values obtained from the traversal.
    • There are no further optimizations needed for this solution.

  9. Handle error cases:

    • The code assumes that the input tree is a valid binary tree with valid nodes.
    • If the input tree is None, the function will return True, considering an empty tree as a valid BST.

  10. Discuss complexity analysis:

    • Let N be the number of nodes in the binary tree.
    • The time complexity of the solution is O(N) as we need to visit each node once.
    • The space complexity is O(N) in the worst case due to the recursive calls and the list of values obtained from the traversal.
    • The solution is efficient and performs well for binary trees with a large number of nodes.
Next Post Previous Post