Aug 17, 2021

Leetcode 98 Validate Binary Search Tree

A valid BST is defined as follows:

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





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





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.

This question can be solved by Depth First Search and Inorder Traversal.
Use In Order Traversal to re-organize the input and get an inordered list, if the inordered list satisfy the binary serach requirements (in order traversal a binary search tree return a continous increament list) we return True else return Fals

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
            if not root:
                return True

            def inOrder(root, order):
                if root is None:
                    return
                inOrder(root.left, order)
                order.append(root.val)
                inOrder(root.right, order)

            order = []
            inOrder(root, order)
            for i in range(1, len(order)):
                if order[i] <= order[i-1]:
                    return False
            return True