leetcode 98 Validate Binary Search Tree

Question source, Given the root of a binary tree, determine if it is a valid binary search tree (BST).

Pre-knowledge

First, we should know the basic idea of a binary search tree. Binary search tree (also ordered binary tree, or sorted binary tree), which refers to an empty tree or a tree have properties as below. * all node values of the left child tree are less than the root node value; * all node values of the right child tree are less than the root node value; * Recursively, left and right child tree are also called binary search tree.

Second, binary tree traversal has three types: pre-order, in-order and post-order. The difference is that the position of checking the root node. * pre-order: root node, left node, right node * in-order: left node, root node, right node * post-order: left node, right node, root node

Problem-solving ideas

With pre-knowledge, we can come up with a solution: This question is equivalent to determining whether the result is in ascending order in the in-order traversal of the tree.

Complexity

  • Time complexity: O(log^n)
    • if the tree is balanced (# left nodes == # right nodes), the depth of the tree is O(log^(n+1)), the access efficiency is \(O(log^n)\); if the tree is absolutely imbalanced, the access efficiency is O(n);
  • Space complexity: O(n)
    • because we need to create a BST, so O(n)

Code

Code file

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        self.prev = None
        return self.helper(root)
    
    def helper(self,root):
        if root is None:
            return True
        if not self.helper(root.left):
            return False
        if self.prev and self.prev.val >= root.val:
            return False
        self.prev = root
        return self.helper(root.right)
        #Runtime: 48 ms, faster than 31.19% of Python3 online submissions for Validate Binary Search Tree.

Summary

  1. All node.vals of the right subtree are greater than the root.val of the right subtree
  2. This question is equivalent to determining whether the result is in ascending order in the in-order traversal of the tree.