BST - 14: Check if there exists a pair for given Sum in BST | Using Set | Using Inorder

Solution - 1
- Traverse BST in preorder manner
- Initialize a Haseset
- If it present, return true, else add current node value in set
- Traverse every node in tree & check above

Time Complexity: O(n)
Space Complexity: O(n)

Solution - 2
- Traverse BST in inorder
- While Traversing in inorder, keepon adding value as well in list as well
- After traversing, we'll have sorted array/list
- Now take two variable start & end, start will point to o index & end will point to last index
- Get sum of values present at start & end index
- If CurrentSum is equal to given sum, return true.
- If CurrentSum is less than given sum, increase start by 1.
- If CurrentSum is greater than given sum, decrese the end by 1

Time Complexity: O(n)
Space Complexity: O(n)

For more info, please see the video.

CHECK OUT CODING SIMPLIFIED

★☆★ VIEW THE BLOG POST: ★☆★

I started my YouTube channel, Coding Simplified, during Dec of 2015.
Since then, I've published over 500+ videos.

★☆★ SUBSCRIBE TO ME ON YOUTUBE: ★☆★

★☆★ Send us mail at: ★☆★

[Makwayne]

You literally covered Two Sum and Two Sum II from Leetcode in this one video. Kudos man, nice content!

[RAJPATEL-nmnz]

There is sol where we can make inorder_forward and backward iterator on tree and space complexity can be reduced to O(h).

[palakkotwani]

Is there any way to improve the TC furthur?

[adityamaurya]

What if sum can be made by 3 nodes number

[crashcartjoe]

Bro also give the problem link so that we practicee