LeetCode 653. Two Sum IV - Input is a BST

Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target.

Example

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

Target = 9

Output: True

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

Target = 28

Output: False

Solution

Traversal BST and try finding pair for each node

• Time Complexity: $O(n \log n)$
• Space Complexity: $O(\log n)$

// Traversal all nodes and check if there is a node 
// whose value = target - this value in the tree.
// Time Complexity: O(n log n)
//   - Traversal: O(n)
//     - Search node in BST: O(log n)
//   => Total: O(n * log n)
// Space Complexity: O(n)
//   - Recursive call stack: O(h) = O(log n)
bool findTarget(TreeNode* root, int k) {
  return findTarget(root, root, k);
}

// Notice: We need to know the root of the BST to search value.
bool findTarget(TreeNode* root, TreeNode* current, int target) {
  if (!root || !current) {
    return false;
  }
  if (findNode(root, current, target - current->val)) {
    return true;
  }
  return findTarget(root, current->left, target) ||
         findTarget(root, current->right, target);
  // return findNode(root, current, target - current->val) ||
  //        findTarget(root, current->left, target) ||
  //        findTarget(root, current->right, target);
}

// Notice: We need to check skip the current node calling this function
// in case its value is counted (e.g., current value = 2, try to find 2).
bool findNode(TreeNode* root, TreeNode* current, int value) {
  if (!root || root == current) {
    return false;
  }
  if (root->val == value) {
    return true;
  }
  if (value < root->val) {
    return findNode(root->left, current, value);
  } else { // value > root->val
    return findNode(root->right, current, value);
  }
  // return root->val == value ||
  //        (value < root->val ? findNode(root->left, current, value) 
  //                           : findNode(root->right, current, value));
}

Two Pointers: Transform BST into sorted array and then search from both sides

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

// Apply the approach for 167. Two Sum II - Input array is sorted here.
// Time Complexity: O(n)
//   - Get sorted value from BST: O(n)
//   - Search pair in sorted array: O(n)
//   => Total: O(n + n) = O(n)
// Space Complexity: O(n)
//   - Array for all node values: O(n)
bool findTarget(TreeNode* root, int k) {
  vector<int> sorted;
  getSorted(root, sorted);
  return twoSum(sorted, k);
}

// Inorder traversal nodes.
void getSorted(TreeNode* root, vector<int>& sorted) {
  if (!root) {
    return;
  }
  getSorted(root->left, sorted);
  sorted.push_back(root->val);
  getSorted(root->right, sorted);
}

bool twoSum(vector<int>& sorted, int target) {
  int left = 0;
  int right = sorted.size() - 1;
  while (left < right) {
    int sum = sorted[left] + sorted[right];
    if (sum == target) {
      return true;
    }
    sum < target ? ++left : --right;
  }
  return false;
}

Hash Table

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

// Apply the approach for 1. Two Sum here.
// Use Hash table to store all visited node.
// Time Complexity: O(n) 
//   - visit all nodes once: O(n) 
// Space Complexity: O(n)
//   - hash table for all nodes: O(n)
bool findTarget(TreeNode* root, int k) {
  unordered_set<int> visited;
  return findTarget(root, k, visited);
}

// Preorder traversal all nodes and search the complement visited before.
bool findTarget(TreeNode* root, int target, unordered_set<int>& visited) {
  if (!root) {
    return false;
  }
  if (visited.find(target - root->val) != visited.end()) {
    return true;
  }
  // we should mark node 'visited' after checking in case it's counted.
  // For example, target = 4, root->val = 2. 
  // If we mark 2 as visited, then we will find 4 - 2 = 2 immediately.
  visited.insert(root->val);
  return findTarget(root->left, target, visited) ||
         findTarget(root->right, target, visited);
}