# [LeetCode binary tree project] verify binary search tree (98)

## 1. Title

Give you the root node of a binary tree, root, to determine whether it is an effective binary search tree.

A valid binary search tree is defined as follows:

• The left subtree of the node only contains the number less than the current node;
• The right subtree of a node contains only the number greater than the current node;
• All left and right subtrees themselves must also be binary search trees.

### 1.1 example

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

• Example 2 2 2 :
• Input: root = [5, 1, 4, null, null, 3, 6]
• Output: false
• Explanation: the value of the root node is 5 5 5, but the value of the right child node is 4 4 4 .

### 1.3 restrictions

• The number of nodes in the tree ranges from [ 1 , 1 0 4 ] [1, 10^4] [1104];
• − 2 31 < = Node.val < = 2 31 − 1 -2^{31} <= \text{Node.val} <= 2^{31} - 1 −231<=Node.val<=231−1 .

## 2. Solution I (recursive middle order traversal)

### 2.1 analysis

Since this is a binary search tree, the ordinal traversal must get a monotonically increasing sequence. Therefore, it is only necessary to perform the ordinal traversal of a given binary tree, judge whether the val value of adjacent nodes meets the monotonically increasing relationship while traversing, if not, return immediately, and maintain an instance attribute self_ Validity is used to indicate whether a given binary tree is a binary search tree. After the middle order traversal returns, the instance property is returned as a result.

### 2.2 realization

from typing import Optional

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

class Solution:
def __init__(self):
self._prev = float('-inf')
self._cur = float('-inf')
self._validity = True

def _is_valid_bst(self, root: TreeNode):
if not root:
return
self._is_valid_bst(root.left)
self._cur = root.val
if self._cur <= self._prev:
self._validity = False
return
self._prev = root.val
self._is_valid_bst(root.right)

def is_valid_bst(self, root: TreeNode) -> Optional[bool]:
self._is_valid_bst(root)
return self._validity

def main():
node5 = TreeNode(6)
node4 = TreeNode(3)
node3 = TreeNode(4, left=node4, right=node5)
node2 = TreeNode(1)
node1 = TreeNode(5, left=node2, right=node3)
root = node1
sln = Solution()
print(sln.is_valid_bst(root))  # False

if __name__ == '__main__':
main()



### 2.3 complexity

• Time complexity: O ( n ) O(n) O(n), where n n n is the number of nodes of the binary tree. Each node of the binary tree can be accessed at most once, so the time complexity is O ( n ) O(n) O(n) .
• Space complexity: O ( n ) O(n) O(n), where n n n is the number of nodes of the binary tree. Because incremental calls implicitly use up to n n n layers, so additional O ( n ) O(n) O(n).

## 3. Solution II (sequential traversal in iteration)

### 3.1 analysis

In addition to the recursive form, the middle order traversal of binary tree also has Order traversal in binary tree in iterative form Based on the latter, the following answers can be given:

from typing import Optional

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

class Solution:
def is_valid_bst(self, root: TreeNode) -> Optional[bool]:
if not isinstance(root, TreeNode):
return
cursor = root
stack = []
prev = float('-inf')
while True:
if cursor:
stack.append(cursor)
cursor = cursor.left
elif stack:
node = stack.pop()
cur = node.val
if cur <= prev:
return False
prev = node.val
cursor = node.right
else:
break
return True

def main():
node5 = TreeNode(6)
node4 = TreeNode(3)
node3 = TreeNode(4, left=node4, right=node5)
node2 = TreeNode(1)
node1 = TreeNode(5, left=node2, right=node3)
root = node1
sln = Solution()
print(sln.is_valid_bst(root))  # False

if __name__ == '__main__':
main()



### 3.3 complexity

• Time complexity: O ( n ) O(n) O(n), where n n n is the number of nodes of the binary tree. Each node of the binary tree can be accessed at most once, so the time complexity is O ( n ) O(n) O(n) .
• Space complexity: O ( n ) O(n) O(n), where n n n is the number of nodes of the binary tree. Because the stack stack used by iteration will be at most n n n elements (at this time, the given binary tree is chain), so additional O ( n ) O(n) O(n).

## 4. Solution 3 (recursive solution based on definition)

### 4.1 analysis

In fact, the analysis of the above two solutions is not very rigorous, because only a binary tree is used here, which is a necessary condition for a binary search tree, that is, the sequence obtained by order traversal must be monotonically increasing; However, it is not further proved that a binary tree is a binary search tree. A sufficient condition is that the middle order ergodic sequence of the binary tree is monotonically increasing. The reason why I didn't give a rigorous analysis is that I don't know for the time being (pit to be filled:). If any friend who happens to see this solution knows, he can discuss it together in the message area.

Therefore, the most rigorous solution is based on the definition of binary search tree, namely:

• If the left subtree of a given binary tree is not empty, the values of all nodes on the left subtree are less than those of its root node;
• If the right subtree of a given binary tree is not empty, the values of all nodes on the right subtree are greater than those of its root node;
• The left and right subtrees of a given binary tree are also binary search trees.

This inspires us to design a recursive function_ check_ Recursive judgment by validity (root, lower, upper). The function indicates that the subtree with root as the root is considered to judge whether the values of all nodes in the subtree are within the range of (lower, upper) (note that it is an open interval). If the value val of the root node is not within the range of (lower, upper), it indicates that it does not meet the conditions and returns directly. Otherwise, we need to continue the recursive call to check whether its left and right subtrees are satisfied. If they are satisfied, it indicates that this is a binary search tree.

According to the nature of binary search tree, when recursively calling the left subtree, we need to change the upper bound to root.val, because the values of all nodes in the left subtree are less than those of its root node. Similarly, when calling the right subtree recursively, we need to change the lower bound to root.val, because the values of all nodes in the right subtree are greater than those of its root node.

The entry of recursive function call is_ check_validity(root, -inf, +inf), inf represents an infinite value.

from typing import Optional

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

class Solution:
def __init__(self):
self._validity = True

def _check_validity(self, root: TreeNode, lower=float('-inf'), upper=float('inf')) -> Optional[bool]:
if not isinstance(root, TreeNode):
return
self._check_validity(root.left, lower, root.val)
if root.val >= upper or root.val <= lower:
self._validity = False
return
self._check_validity(root.right, root.val, upper)

def is_valid_bst(self, root: TreeNode) -> Optional[bool]:
self._check_validity(root)
return self._validity

def main():
node5 = TreeNode(6)
node4 = TreeNode(3)
node3 = TreeNode(4, left=node4, right=node5)
node2 = TreeNode(1)
node1 = TreeNode(5, left=node2, right=node3)
root = node1
sln = Solution()
print(sln.is_valid_bst(root))  # False

if __name__ == '__main__':
main()


### 4.3 complexity

• Time complexity: O ( n ) O(n) O(n), where n n n is the number of nodes of the binary tree. During recursive invocation, each node of the binary tree can be accessed at most once, so the time complexity is O ( n ) O(n) O(n) .
• Space complexity: O ( n ) O(n) O(n), where n n n is the number of nodes of the binary tree. Recursive functions need to allocate stack space for each layer of recursive functions in the recursive process, so additional space is required here, and the space depends on the depth of recursion, that is, the height of binary tree. In the worst case, the binary tree is a chain, and the height of the tree is n n n. Recursive deepest reach n n n layers, so the space complexity in the worst case is O ( n ) O(n) O(n) .

Keywords: Algorithm leetcode

Added by spyke01 on Sat, 20 Nov 2021 10:20:44 +0200