CODEWITHSUNDEEP
algorithmtreebinary-search-tree
Peyman Tahghighi
Peyman Tahghighi

Reputation: 77

How to check if binary tree is BST in O(nlgn)?

I have a problem in my exercise that want to give an algorithm that checks whether a binary tree is BST or not.

It also wants to solve it with divide and conquer so I think my recursive function should be something like this: 

T(n) = 2T(n/2) + O(n)

but I have no idea how to design the merge part to be in the order of O(n).

Did anyone get any idea?

Upvotes: 0

Views: 109

Answers (1)

Will Ness
Will Ness

Reputation: 71065

Tree traversal is O(n). Sortedness check of a list is O(n). O(n) is in O(n log n).

Going with what you said though, the merge part should be O(1), not O(n), again giving you an O(n) solution overall: if the left sub-tree is a BST, and the right sub-tree is a BST, and left sub-root is smaller than root, and root is no larger then right sub-root, then this tree is a BST:

T(n) = T(m) + T(n-m-1) + T(1)    where   m < n   is the count of the left subtree

Plus the obvious edge-case handling of empty sub-trees.

Upvotes: 4

Related Questions