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