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 compute

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 :

compute

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.

postorder

Here the nodes are enumerated in the order you visit them, and you could follow 1-2-3-4-5 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.

postorder

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.

Analysis written by @liaison and @andvary