Solution
Tree definition
First of all, here is the definition of the TreeNode
which we would use.
Intuition
On the first sight, the problem is trivial. Let's traverse the tree
and check at each step if node.right.val > node.val
and
node.left.val < node.val
. This approach would even work for some
trees
The problem is this approach will not work for all cases. Not only the right child should be larger than the node but all the elements in the right subtree. Here is an example :
That means one should keep both upper
and lower limits for each node while traversing the tree,
and compare the node value not
with children values but with these limits.
Approach 1: Recursion
The idea above could be implemented as a recursion. One compares the node value with its upper and lower limits if they are available. Then one repeats the same step recursively for left and right subtrees.
!?!../Documents/98_LIS.json:1000,462!?!
Complexity Analysis
 Time complexity : since we visit each node exactly once.
 Space complexity : since we keep up to the entire tree.
Approach 2: Iteration
The above recursion could be converted into iteration, with the help of stack. DFS would be better than BFS since it works faster here.
Complexity Analysis
 Time complexity : since we visit each node exactly once.
 Space complexity : since we keep up to the entire tree.
Approach 3: Inorder traversal
Algorithm
Let's use the order of nodes in the
inorder traversal
Left > Node > Right
.
Here the nodes are enumerated in the order you visit them,
and you could follow 12345
to compare different strategies.
Left > Node > Right
order of inorder traversal
means for BST that each element should be smaller
than the next one.
Hence the algorithm with time complexity and space complexity could be simple:

Compute inorder traversal list
inorder
. 
Check if each element in
inorder
is smaller than the next one.
Do we need to keep the whole
inorder
traversal list?
Actually, no. The last added inorder element is enough to ensure at each step that the tree is BST (or not). Hence one could merge both steps into one and reduce the used space.
Implementation
Complexity Analysis

Time complexity : in the worst case when the tree is BST or the "bad" element is a rightmost leaf.

Space complexity : to keep
stack
.