Validate Binary Search Tree

Problem Id: 98 Difficulty: Medium Tag: Tree Tag: Depth-first Search


Intuition

This problem could be solved basically by doing an in-order traversal of the tree and to see if we visit each node with an increasing order.

Please notice that, a BST does not have one value more than twice.

Solution


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        self.current = float('-inf')
        self.increasing = True
        self.inorder_traversal(root)
        return self.increasing

    def inorder_traversal(self, node):
        if node is None:
            return
        self.inorder_traversal(node.left)
        if node.val <= self.current:
            self.increasing = False
        self.current = node.val
        self.inorder_traversal(node.right)