653. Two Sum IV - Input is a BST

Hello, reader 👋🏽 ! Welcome to day 9 of the series on Problem Solving. Through this series, I aim to pick up at least one question everyday and share my approach for solving it.

Today, I will be picking up LeetCode's daily challenge problem: 2Sum 4 - Input is a BST.

🤔 Problem Statement

• Given the root of a binary search tree and a target k, you have to find if there exists any two nodes whose sum add up to k. If they exist, return true, else false.
• E.g.:
  • root = [5,3,6,2,4,null,7], k = 9 => true
  • root = [5,3,6,2,4,null,7], k = 1 => false

Link to the problem: 2Sum 4 - Input is a BST.

💬 Thought Process - Brute Force Approach

• The moment I saw this problem, hashing came to my mind. I didn't even complete reading the problem.
• But the naive approach would be to look through every pair of nodes for a chosen root.
• We perform a binary search to find k - nodeValue from the root of the tree.

👩🏽‍💻 Solution - Brute Force Approach

• Below is the code for the approach discussed above:

  class Solution {
    public boolean findTarget(TreeNode root, int k) {
        return dfs(root, root, k);
    }
  
    // You need to maintain the startNode for whose complement you're searching 
    // Since every search for the complement would begin from the root,
    // You need to avoid comparing with the same node again
    private boolean dfs(TreeNode root, TreeNode startNode, int target) {
        if(startNode == null) {
            return false;
        }
        // Now search for the complement of this node
        boolean result = search(root, startNode, target-startNode.val);
        if(result) {
            return true;
        }
  
        return dfs(root, startNode.left, target) || 
          dfs(root, startNode.right, target);
    }
  
    private boolean search(TreeNode root, TreeNode startNode, int target) {
        if(root == null) {
            return false;
        }
  
        if(root.val == target && root != startNode) {
            return true;
        }
        if(target < root.val) {
            return search(root.left, startNode, target);
        }
        return search(root.right, startNode, target);
    }
  }
  

  Time Complexity: O(nh) 
    - h = height of the tree. 
      - In the worst case height would be `O(n^2)` if the tree is skewed or 
      - on average height would be`O(og n)` 
  Space Complexity: O(h) 
    - h = height of tree (log n).
  

💬 Thought Process - Inorder Traversal and Two Pointers

• Since the inorder traversal of a BST returns the node values in sorted order, we can make use of this.
• We save the inorder traversal in a list and use two pointers approach - keep a left and right pointer in the list, compare the sum of left and right elements with target.
  • If this sum is equal to target, we return true.
  • If this sum < target, then we increase the left pointer.
  • Else, we decrease the right pointer.
• We keep repeating this until the the left and right pointers become equal.

👩🏽‍💻 Solution - Inorder Traversal and Two Pointers

• Below is the code for the approach discussed above:

  class Solution {
    List<Integer> traversal;
    public boolean findTarget(TreeNode root, int k) {
        traversal = new ArrayList();
        inorderTraversal(root);
  
        int left = 0, right = traversal.size()-1;
        while(left < right) {
            int sum = traversal.get(left) + traversal.get(right);
            if(sum == k) {
                return true;
            }
            if(sum > k) {
                right--;
            }
            else {
                left++;
            }
        }
  
        return false;
    }
  
    private void inorderTraversal(TreeNode root) {
        if(root == null) {
            return;
        }
  
        inorderTraversal(root.left);
        traversal.add(root.val);
        inorderTraversal(root.right);
    }
  }
  

  Time Complexity: O(n)
    - n = number of nodes in the tree
  Space Complexity: O(n)
    - n = number of nodes, we are saving the inorder traversal in a list
  

💬 Thought Process - Hash Set

• If you've solved the 2 Sum problem on arrays, then this would be the first approach you'll probably think of.
• The basic idea is to keep track of every node value in a set. When you are processing a root node, you check if the complement of the current root value, i.e.,target-currentRootValue exists in the set. If yes, you return true.

👩🏽‍💻 Solution - Hash Set

• Below is the code for the approach discussed above:

  class Solution {
      HashSet<Integer> seen;
      public boolean findTarget(TreeNode root, int k) {
          seen = new HashSet();
          return dfs(root, k);
      }
  
      private boolean dfs(TreeNode root, int target) {
          if(root == null) {
              return false;
          }
  
          if(seen.contains(target - root.val)) {
              return true;
          }
          seen.add(root.val);
          return dfs(root.left, target) || dfs(root.right, target);
      }   
   } 
  }
  

  Time Complexity: O(n)
    - n = number of nodes in the tree
  Space Complexity: O(n)
    - n = number of nodes, we are keeping track of all node values in a set
  

💬 Thought Process - Binary Search Tree Iterator

• This is the trickiest solution and probably what an interviewer is expecting in an interview. Unfortunately, this is not at all intuitive. But, I'll try to explain it as easily as possible.
• But, if you want to understand this solution, you will have to checkout the problem of Binary Search Iterator, which is the motivation behind this solution.
• Here's the idea: we use the fact that the BST produces a list of sorted values from inorder traversal.
• Instead of keeping the values of all n nodes, we simply keep track of at most h nodes, where h = height of the tree.
• We define a custom class BSTIterator, that let's us iterate from left (sorted order) and right (reverse sorted order) from the inorder traversal.
• We will store 2 separate stacks, one from left subtree and other from right subtree -> stackL and stackR.
• At every point, the top most value of stackL would be the smallest element in the left tree from the current node.
• Similarly that of stackR would be largest element in the right subtree from the current node.

• This sort of works like left and right pointers. We compare the sum of top values from both stacks with target:

  • If the sum == target: return true
  • If the sum > target: that means we will have to move towards the left side of the top node in stackR. We add all the right subtree nodes to the left of the popped node.
  • If the sum < target: that means we will have to move the right side of the top node in stackL. We add all the left subtree nodes to the right of the popped node.

• It sort of works like this:

👩🏽‍💻 Solution - Binary Search Tree Iterator

• Below is the code for the approach discussed above:

  class BSTInorder {
      private Stack<TreeNode> left, right;
  
      BSTInorder(TreeNode root) {
          left = new Stack();
          right = new Stack();
          pushAllLeft(root);
          pushAllRight(root);
      }
  
      private void pushAllLeft(TreeNode root) {
          TreeNode temp = root;
          while(temp != null) {
              left.push(temp);
              temp = temp.left;
          }
      }
  
      private void pushAllRight(TreeNode root) {
          TreeNode temp = root;
          while(temp != null) {
              right.push(temp);
              temp = temp.right;
          }
      }
  
      private int next() {
          TreeNode top = left.pop();
          pushAllLeft(top.right);
          return top.val;
      }
  
      private int before() {
          TreeNode top = right.pop();
          pushAllRight(top.left);
          return top.val;
      }
  
      public boolean findTarget(int k) {
          int l = next();
          int r = before();
          while(l < r) {
              int sum = l+r;
              if(sum == k) {
                  return true;
              }
              if(sum > k) {
                  r = before();
              }
              else {
                  l = next();
              }
          }
          return false;
      }
  }
  
  class Solution {
      public boolean findTarget(TreeNode root, int k) {
          BSTInorder bstInorder = new BSTInorder(root);
          return bstInorder.findTarget(k);
      }
  }
  

  Time Complexity: O(n)
    - next(), before(): O(1) operation
    - findTarget: O(h)
        - In the worst case, O(n) and average case O(log n)
  Space Complexity: O(h)
    - h = height of tree, we are keeping track all the nodes of the same height. Worst case O(n), average: O(log n)
  

• The code for all the above approaches can be found in this repo -> Two Sum IV - Input is a BST.

Conclusion

That's a wrap for today's problem. If you liked my explanation then please do drop a like/ comment. Also, please correct me if I've made any mistakes or if you want me to improve something!

Thank you for reading!