Two Sum in BST in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Two Sum in BST with target 9

Given the BST and target = 9, what is the output of the Two Sum function that returns true if two nodes sum to the target?

DSA Typescript

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val === undefined ? 0 : val;
    this.left = left === undefined ? null : left;
    this.right = right === undefined ? null : right;
  }
}

function findTarget(root: TreeNode | null, k: number): boolean {
  const set = new Set<number>();
  function dfs(node: TreeNode | null): boolean {
    if (!node) return false;
    if (set.has(k - node.val)) return true;
    set.add(node.val);
    return dfs(node.left) || dfs(node.right);
  }
  return dfs(root);
}

// BST:
//       5
//      / \
//     3   6
//    / \   \
//   2   4   7

const root = new TreeNode(5,
  new TreeNode(3,
    new TreeNode(2),
    new TreeNode(4)
  ),
  new TreeNode(6,null,new TreeNode(7))
);

console.log(findTarget(root, 9));

A true

B false

C undefined

D TypeError

💡 Hint

Think about checking if the complement (target - current node value) exists in a set while traversing.

The function traverses the BST and stores visited node values in a set. When it finds a node where target - node.val is already in the set, it returns true. Here, 2 and 7 sum to 9, so output is true.

🧠 Conceptual

intermediate

What data structure is best for checking complements in Two Sum in BST?

In the Two Sum problem on a BST, which data structure allows efficient checking if the complement (target - current node value) has been seen before?

A Array

B Queue

C Stack

D Set

💡 Hint

You want fast lookup to check if a value exists.

A Set provides O(1) average time complexity for lookup, making it ideal to check if the complement exists while traversing the BST.

🔧 Debug

advanced

Identify the error in this Two Sum in BST code snippet

What error will this TypeScript code produce when run?

DSA Typescript

function findTarget(root: TreeNode | null, k: number): boolean {
  const set = new Set<number>();
  function dfs(node: TreeNode | null): boolean {
    if (!node) return false;
    if (set.has(k - node.val)) return true;
    set.add(node.val);
    return dfs(node.left) && dfs(node.right);
  }
  return dfs(root);
}

A Always returns false

B Returns true only if both left and right subtrees have pairs summing to k

C Returns true if two nodes sum to k

D Throws a runtime error

💡 Hint

Check the logical operator used to combine recursive calls.

Using && means both left and right subtree calls must be true to return true, which is incorrect. It should be || to return true if either subtree has a valid pair.

❓ Predict Output

advanced

Output of Two Sum in BST with target 28

Given the BST below and target = 28, what is the output of the Two Sum function?

DSA Typescript

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val === undefined ? 0 : val;
    this.left = left === undefined ? null : left;
    this.right = right === undefined ? null : right;
  }
}

function findTarget(root: TreeNode | null, k: number): boolean {
  const set = new Set<number>();
  function dfs(node: TreeNode | null): boolean {
    if (!node) return false;
    if (set.has(k - node.val)) return true;
    set.add(node.val);
    return dfs(node.left) || dfs(node.right);
  }
  return dfs(root);
}

// BST:
//       10
//      /  \
//     5    15
//    / \     \
//   3   7     18

const root = new TreeNode(10,
  new TreeNode(5,
    new TreeNode(3),
    new TreeNode(7)
  ),
  new TreeNode(15,null,new TreeNode(18))
);

console.log(findTarget(root, 28));

A true

B TypeError

C undefined

D false

💡 Hint

Check if any two nodes sum to 28.

The function traverses the BST and stores visited node values in a set. When it finds a node where target - node.val is already in the set, it returns true. Here, 10 and 18 sum to 28, so output is true.

🧠 Conceptual

expert

Time complexity of Two Sum in BST using DFS and Set

What is the time complexity of the Two Sum in BST algorithm that uses DFS traversal and a Set to check complements?

A O(n^2)

B O(n log n)

C O(n)

D O(log n)

💡 Hint

Consider that each node is visited once and set lookups are O(1).

The algorithm visits each node once (O(n)) and performs O(1) lookup in the set, so total time is O(n).