# 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 file

## 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.