Validate Binary Search Tree

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

Pattern

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

Approaches

Explanation

A binary tree is a binary search tree if every node value is within the range defined by its ancestors. For example, the left child p.left of a node p must be less than p.val. The grandchild p.left.right must be between p.left.val and p.val.

We can recursively check each node to see if it is with in range. Initially, the range is \((-\infty, \infty)\). When we go left, we update the upper bound to be the parent node’s value. When we go right, we update the lower bound to be the parent node’s value. If the node’s value is not within the range, the result is False. Otherwise, the result is True.

Code

from __future__ import annotations

from collections import deque


class TreeNode:
    """Node in a binary tree."""

    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

    @classmethod
    def from_list(cls, vals: list[int | None]) -> TreeNode | None:
        if not vals:
            return None

        root = cls(vals[0])
        queue = deque([root])
        children = iter(vals[1:])

        while queue:
            node = queue.popleft()
            for side in ("left", "right"):
                val = next(children, None)
                if val is not None:
                    child = cls(val)
                    setattr(node, side, child)
                    queue.append(child)

        return root

    def to_list(self) -> list:
        result = []
        queue = [self]
        while queue:
            node = queue.pop(0)
            if node:
                result.append(node.val)
                queue.append(node.left)
                queue.append(node.right)
            else:
                result.append(None)
        while result and result[-1] is None:
            result.pop()
        return result


def is_valid_bst(node, left, right):
    if node is None:
        return True

    if not (left < node.val < right):
        return False

    return is_valid_bst(node.left, left, node.val) and is_valid_bst(
        node.right, node.val, right
    )


def isValidBST(root: TreeNode | None) -> bool:
    """Return whether ``root`` is a valid binary search tree."""
    return is_valid_bst(root, float("-inf"), float("inf"))

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

Complexity

\(n\) is the number of nodes in the tree, and \(d\) is the maximum depth of the tree

Measure

Complexity

Notes

Time

\(O(n)\)

visit every node in the tree

Auxiliary Space

\(O(d)\)

recursive call stack
class validate_binary_search_tree__recursive.TreeNode(val=0, left=None, right=None)

Bases: object

Node in a binary tree.

classmethod from_list(vals: list[int | None]) → TreeNode | None
to_list() → list
validate_binary_search_tree__recursive.is_valid_bst(node, left, right)
validate_binary_search_tree__recursive.isValidBST(root: TreeNode | None) → bool

Return whether root is a valid binary search tree.