Inorder Traversal and Two-Pointer Technique
Inorder traversal of BST gives elements in sorted order. We are going to traverse the BST in inorder manner and keep storing every element inside an array. When we obtain an ordered arrangement from the inorder traversal then we employ two pointer technique to identify pairs whose summation results into target sum by taking one pointer at beginning of array and another at end or rightmost position.
Example: This example shows the use of the above-explained approach.
class TreeNode {
constructor(val) {
this.val = val;
this.left = null;
this.right = null;
}
}
function findPairWithSumInBST(root, sum) {
// Inorder traversal to convert BST to a sorted array
function inorderTraversal(node, arr) {
if (!node) return;
inorderTraversal(node.left, arr);
arr.push(node.val);
inorderTraversal(node.right, arr);
}
const arr = [];
inorderTraversal(root, arr);
// Two-pointer technique
let left = 0;
let right = arr.length - 1;
while (left < right) {
const currentSum = arr[left] + arr[right];
if (currentSum === sum) {
return [arr[left], arr[right]]; // Pair found
} else if (currentSum < sum) {
left++;
} else {
right--;
}
}
return null; // No pair found
}
// Example usage
const root = new TreeNode(5);
root.left = new TreeNode(3);
root.right = new TreeNode(8);
root.left.left = new TreeNode(1);
root.left.right = new TreeNode(4);
root.right.left = new TreeNode(7);
root.right.right = new TreeNode(10);
const sum = 9;
const pair = findPairWithSumInBST(root, sum);
console.log(pair); // Output: [1, 8]
Output
[ 1, 8 ]
Time complexity: O(n)
Space complexity: O(n)
Find a Pair with a Given Sum in BST using JavaScript
Given a target sum and Binary Search Tree (BST), we have to write a function to find out the pair of nodes in BST whose values will sum up to this given sum. We must give these two numbers as an array that adds up to get this target sum. If there is no such number pair, return null.
Example:
Input: sum = 28, given BST
Output: [1,8]
BST
Below are the approaches to find a pair with a given sum in BST using JavaScript:
Table of Content
- Inorder Traversal and Two-Pointer Technique
- Iterative Two-Pointer Approach Using BST Iterators