Validate a binary search tree#

Levels: level-2

Data structures: tree

Algorithms: dfs

Practice Link#

Description#

Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a 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.

Examples#

1    2
2   / \
3  1   3
4
5Input: [2,1,3]
6Output: true

1    5
2   / \
3  1   4
4     / \
5    3   6
6
7Input: [5,1,4,null,null,3,6]
8Output: false
9Explanation: The root node's value is 5 but its right child's value is 4.

Python Solution#

 1# Definition for a binary tree node.
 2class TreeNode(object):
 3    def __init__(self, x):
 4        self.val = x
 5        self.left = None
 6        self.right = None
 7
 8
 9class Solution:
10    # Recursive solution
11    def isValidBST(self, root):
12        """
13        :type root: TreeNode
14        :rtype: bool
15        """
16        def helper(node, lower=float('-inf'), upper=float('inf')):
17            if not node:
18                return True
19
20            val = node.val
21            if val <= lower or val >= upper:
22                return False
23
24            if not helper(node.right, val, upper):
25                return False
26            if not helper(node.left, lower, val):
27                return False
28            return True
29
30        return helper(root)
31
32    # Use inorder traversal
33    def isValidBSTInorder(self, root):
34        """
35        :type root: TreeNode
36        :rtype: bool
37        """
38        stack, inorder = [], float('-inf')
39
40        while stack or root:
41            while root:
42                stack.append(root)
43                root = root.left
44            root = stack.pop()
45            # If next element in inorder traversal
46            # is smaller than the previous one
47            # that's not BST.
48            if root.val <= inorder:
49                return False
50            inorder = root.val
51            root = root.right
52
53        return True