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

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');" ...

LOVE THE WAY SINGLETON PATTERN CAN BE DESIGNED ! WOWW...

To implement Singleton pattern, we have different approaches : 1.Eager initialization: In this method the instance of clss is created at loading time .As whenever in java there is a requirement of species at loading time we first remember of Static keyword. package com.questprogram.singleton; public class EagerInitializedSingleton { private static final EagerInitializedSingleton instance = new EagerInitializedSingleton(); //private constructor to avoid client applications to use constructor private EagerInitializedSingleton(){} public static EagerInitializedSingleton getInstance(){ return instance; } } 2. Static block initialization Static Block initialization implementation is similar to eager initialization, except that instance of class is created in the static block that provides option for exception handling. package com.questprogram.singleton; public class StaticBlockSingleton { private static StaticBlockSingleto...

Design Discussion over Microservices Adaption

Terms that are most commonly used in any microservices architecture Don't worry after watching so many new terms as below : Saga Pattern Bounded context Eventual consistency Event Command Execution Event broker CDC (change data capture) event managment Domain driven design Event driven design CQRS (Command query responsibility segregation) Rollback operation Asynchronous Callback operation Fault tolerance :Bulk Head & Circuit breaker Open API configurations Centralized logging ELK Stats aggregation Aggregates in Domain Driven Design FAT Domain VS Anemic Domain Ubiquitous Language Event sourcing Event replay Scatter-Gather Pattern Saga Pattern: A pattern which is the heart soul of any microservice architecture ,it is used to manage data consistency across multiple microservices in distributed transaction .It performs a sequence of local transactions which perform updation operation in services & publish a message or trigger the event. T...

TechBlog

Search This Blog