Question

Describe an algorithm that checks if a given binary tree T is a binary search tree. Analyze your algorithm by giving its asymptotic runtime. Show your work.

Answer 1

Efficient algorithm will be to use in order traversal:

Algorithm :

1. do in-order traversal of the tree

2. check if the array after traversal is sorted or not ? if sorted then BST otherwise NOT a BST

Complexity :

Line 1 : O(n)

Line2 : O(n)

hence O(n)

for more clarification please comment.