Esta questão já tem uma resposta aqui:

Hoje eu tive uma entrevista onde me pediram para escrever um programa que pega uma Árvore Binária e retorna true se também é uma Árvore de Busca Binária falsa.

My Approach1: Realize um percurso em ordem e armazene os elementos no tempo O (n). Agora escaneie a matriz / lista de elementos e verifique se o elemento at iº índice é maior que elemento em (i + 1)º índice. Se tal condição for encontrada, retorne false e saia do loop. (Isso leva O (n) tempo). No final, retorne verdadeiro.

Mas esse cavalheiro queria que eu fornecesse uma solução eficiente. Eu tentei, mas não tive sucesso, porque para descobrir se é um BST eu tenho que verificar cada nó.

Além disso, ele estava me apontando para pensar sobre recursão. My Approach 2: Um BT é um BST se para qualquer nó N N-> left for <N e N-> right> N, e o sucessor em ordem do nó esquerdo de N for menor que N e o sucessor em ordem do nó direito de N é maior que N e as subárvores esquerda e direita são BSTs.

Mas isso vai ser complicado e o tempo de execução não parece ser bom. Por favor, ajude se você conhece alguma solução ideal.