DS PROBLEM :Find a pair with given sum in a BST(Binary Search Tree)

Problem : Given a Balanced Binary Search Tree and a target sum, write a function that returns true if there is a pair with sum equals to target sum, otherwise return false. Expected time complexity is O(n) and only O(Logn) extra space can be used. Any modification to Binary Search Tree is not allowed. Note that height of a Balanced BST is always O(Logn).

Solution: There are two approaches to solve the problem

The Brute Force Solution is to consider each pair in BST and check whether the sum equals to X. The time complexity of this solution will be O(n^2).

A Better Solution is to create an auxiliary array and store Inorder traversal of BST in the array. The array will be sorted as Inorder traversal of BST always produces sorted data. Once we have the Inorder traversal, we can pair in O(n) time (See this for details). This solution works in O(n) time, but requires O(n) auxiliary space.

Comments

Median of Two Sorted Arrays

Problem Understanding: In simpler terms, you need to find the middle value of the combined , sorted array formed by merging nums1 and nums2. If the combined array has an even number of elements, you should return the average of the two middle values. If it has an odd number of elements, you should return the middle value itself. Approach 1: Merge and Sort Create a new array with a size equal to the total number of elements in both input arrays. Insert elements from both input arrays into the new array. Sort the new array. Find and return the median of the sorted array. Time Complexity In the worst case TC is O((n + m) * log(n + m)) . Space Complexity O(n + m) , where ‘n’ and ‘m’ are the sizes of the arrays. Approach 2: Two-Pointer Method Initialize two pointers , i and j, both initially set to 0. Move the pointer that corresponds to the smaller value forward at each step. Continue moving the pointers until you have proce...

Difference between String ,StringBuffer & StringBuilder?

Run this simple java program and create scenerio of String object creation in your mind.You will see huge difference than expectation. I would recommend to first try on your own then follow the solution . As you execute the above line of codes in your Java Runtime Environment .As compiler read the lines .In case of String a= new String("Hello"); As it will allow compiler to create a new string object .It is always mandatory for compiler to allocate a memory space in heap whenever new keyword is used.So String class object created successfully in heap with reference variable a.And a very important point need to be noted down that here "new String("Hello');" ...

AngularJs/javascript and Angular/typescript (version 2/4/latest) have a series of difference.

AngularJs vs Angular (Typescript) On basis of process of compilation ANGULARJS : Angular Js compiler traverses the DOM looking for attributes . It takes two phase for compilation where initial phase traverse the DOM and collect all of the directives. The result is a linking function. Next phase evolves combine the directives with a scope and produce a live view. Any changes in the scope model are reflected in the view, and any user interactions with the view are reflected in the scope model. This makes the scope model the single source of truth.

TechBlog

Search This Blog