Time complexity to check for binary search tree

What is the time complexity to check whether a binary tree binary search tree or not?

Habib Mohammad Khan @habibkhan
20 Sep 2016 09:48 pm

There are 2 approaches to this.

Approach 1:

Using basic definition of BST , we check for each node comparing it with left and right child recursively.If the node value is greater than left child and smaller than right child , then we proceed recursively and check for the same property of BST for left and right children and so on.So at a time we are comparing 1 node with its left and right child , so 2 comparisions at a time , which is a constant.Hence the recurrence relation for this :

T(n) = 2T(n/2) + c . Here 2T(n/2) since we are checking the same property for both left and right subtree and the tree is balanced.

In case tree is left or right skewed ,

T(n) = T(n-1) + c

In both cases , we get complexity = O(n).

Hence , best case = worst case for this problem.

Hence time complexity = θ(n)


Approach 2:

Using the fact that inorder traversal of BST gives increasing order.We do the inorder traversal of binary tree which takes O(n) time.Then we check the result of traversal whether it is sorted or not which can be done in 1 scan of the result.

Hence overall complexity = θ(n)