2-sum BST | Find a pair with given sum in a BST | 2 Methods
Given the root of a Binary Search Tree and a target number k, return true if there exist two elements in the BST such that their sum is equal to the given target.
I have explained 2 methods to solve this.
Method 1: Using Inorder traversal and a set. O(n) time complexity, O(n) space complexity
Method 2: Using 2 pointer technique. This is slightly more efficient than method I in terms of space complexity. O(n) time complexity, O(logn) space complexity
Source code: https://github.com/fit-coder/fitcoder...
00:00 Introduction
00:07 Problem explanation
01:05 Method 1: Inorder + Set
05:10 Method 2: Two pointer Approach
15:34 Implementation
-------------------------------------------------------------
I live in New Delhi and love explaining programming concepts. I have done M.Tech(BITS Pilani) + B.Tech(PEC, Chandigarh) in Computer Science and am currently working as a software engineer in a MNC.
If you like my content, please like, share my videos and subscribe to the channel.
-------------------------------------------------------------
For other BST tutorials, please refer to the below links:
Introduction to BST: • Introduction to Binary Search Trees | BST ...
Delete node in BST: • Delete a node from Binary Search Tree | BST
LCA in BST: • Lowest Common Ancestor (LCA) in Binary Sea...
Validate BST: • Check if Binary Tree is Binary Search Tree...
Sorted array to Balanced BST: • Convert Sorted Array To Balanced Binary Se...
Valid BST from preorder: • Valid BST from Preorder | Verify Preorder ...
For other tree tutorials, please refer to the below playlist:
• Tree Data Structures
For in-depth Graph theory and implementation details, please refer to the below playlist:
• Graph Algorithms
#DataStructure,#Trees,#FitCoder,#Algorithm,#competitiveprogramming,#binarytree,#binarysearchtree