# 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

1 | class Solution: |

## Summary

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