Binary Search Tree


#tree
- 1 minutes read - 139 words

Definition

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.

Validating a BST

  • Get the inorder representation
  • Check if it is sorted
# 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 inorder(self, root):
        order = []
        
        if root == None:
            return order
        
        order.extend(self.inorder(root.left))
        order.append(root.val)
        order.extend(self.inorder(root.right))
        
        return order
    
    def isValidBST(self, root: TreeNode) -> bool:
        order = self.inorder(root)
        if len(order) < 2:
            return True
        for i in range(1, len(order)):
            if order[i] <= order[i-1]:
                return False
        return True