TechBlog

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).