Binary Search Tree

Question

Given a binary search tree and a number ‘x’. What is the best time complexity to find the sum of two numbers in an array is equal to given number x?

Answer 1

Binary search tree is applied when array is sorted . otherwise binary search tree not work.

Binary search will take O(nlogn) time only since take any element and find another element using logn comparision.

Another method :

1) Initialize Binary Hash Map M[] = {0, 0, ...}
2) Do following for each element A[i] in A[]
   (a)	If M[x - A[i]] is set then print the pair (A[i], x - A[i])
   (b)	Set M[A[i]]

Take O(n) time only.

Answer 2

We already have a binary search tree. Instead of storing in array. Just store each number in hash table while traversing the tree and again traverse the tree and check if x-A[i] exists in hash table. Saves array space and used just 2 iterations. This takes O(N) time.

Comments

Sorting using array . and then use hash table . is there any limitaion on number of data structure.?

---

"Given a binary search tree and a number ‘x’."

You already have a BST. Perform inorder traversal of this BST and store it in an array. Traversal takes O(N) time. This array will always be sorted. Now traverse this array and store all the numbes in a hash table. This step again takes O(N) time. Now traverse the array one more time and for each element A[i], check if x-A[i] is present in the hash table or not. Total time O(N) + O(N) + O(N) = 3O(N). I don't think there is a solution with runtime better than O(N). Also, the question doesnt place any restriction on the amount of space used. So this technique is correct.

---

M not saying your method is incorrect i m saying just use simple hash table .

---

@anirudh Yes. thats better. Instead of storing in array. Just store in hash table while traversing the tree and again traverse the tree and check if x-A[i] exists in hash table. Saves array space and used just 2 iterations. Thanks.