:orphan:

Validate Binary Search Tree
===========================

.. highlight:: none

Problem
-------
https://leetcode.com/problems/validate-binary-search-tree/

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 keys **strictly
  less than** the node's key.
- The right subtree of a node contains only nodes with keys **strictly
  greater than** the node's key.
- Both the left and right subtrees must also be binary search trees.

 

**Example 1:**

|image1|

::


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

**Example 2:**

|image2|

::


   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.

 

**Constraints:**

- The number of nodes in the tree is in the range
  ``[1, 10``\ :sup:```4```\ ``]``.
- ``-2``\ :sup:```31```\ ``<= Node.val <= 2``\ :sup:```31```\ ``- 1``

.. |image1| image:: https://assets.leetcode.com/uploads/2020/12/01/tree1.jpg
.. |image2| image:: https://assets.leetcode.com/uploads/2020/12/01/tree2.jpg

.. highlight:: python

Pattern
-------
Tree, Depth-First Search, Binary Search Tree, Binary Tree

Approaches
----------

.. tab-set::

    .. tab-item:: Recursive

        **Code**

        .. literalinclude:: ../problems/medium/validate-binary-search-tree/validate_binary_search_tree__recursive.py
            :language: python
            :lines: 9-

        **Test**

        >>> from validate_binary_search_tree__recursive import isValidBST, TreeNode
        >>> isValidBST(TreeNode.from_list([2, 1, 3]))
        True
        >>> isValidBST(TreeNode.from_list([5, 1, 4, None, None, 3, 6]))
        False

        .. autoclass:: validate_binary_search_tree__recursive.TreeNode
           :members:
           :show-inheritance:
           :undoc-members:

        .. autofunction:: validate_binary_search_tree__recursive.is_valid_bst

        .. autofunction:: validate_binary_search_tree__recursive.isValidBST