98.Validate Binary Search Tree

Tags: [inorder], [inorder_traversal], [stack], [tree], [binary_tree], [binary_search_tree], [BST]

Com: {fb}

Link: https://leetcode.com/problems/validate-binary-search-tree/\#/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.

Example 1:

    2
   / \
  1   3

Binary tree[2,1,3], return true.

Example 2:

    1
   / \
  2   3

Binary tree[1,2,3], return false.

Solution: Inorder Traversal, Stack

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

class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return True

        # inorder traversal
        stack = []
        prev = None
        curr = root

        while curr or stack:
            if curr:
                stack.append(curr)
                curr = curr.left
            else:
                curr = stack.pop()
                if prev and prev.val >= curr.val:
                    return False

                prev = curr
                curr = curr.right

        return True

Revelation:

• We cannot just check the root.left and root.right, then do recursion on the left subtree, and right subtree, because there exists the following case:

Note:

• Time complexity = O(n), n is the number of nodes of the given tree.
• Space complexity = O(n), n is the number of nodes of the given tree. There seems no way to use O(1) space to achieve the goal, because even we use the recursion, the recursion will let system to keep a stack, which also cost space.