Write a function that takes a BinaryTree and validates if it is a valid BinarySearchTree. Assume the tree contains no duplicate values.

Question

simple_coder · Accepted Answer

Do an inorder traversal and check if the elements are sorted.

Sigiloso · Answer

Write a recursive function that take the node as input and return three values:
1, If the tree rooted with this node is BST or not,
2, the max/min of the tree rooted with this node.

If the node has children, the tree rooted with this node is a BST if:
1, Both its left and right children are BST
2, Max value of left < node < min value of right

If the node has no childres, return (tree, node value, node value)

Amazon

Pergunta de entrevista da empresa Amazon

Respostas da entrevista

Empresas seguidas

Buscas de vagas