DKodeTree Small Logo
DKodeTreeWhere logic takes root...!
Two Sum IV - Input is a BST - Solution
Solutions and explanations
Link to Problem StatementView on GitHub

We perform a depth-first search (DFS) of the tree while maintaining a set of values that have already been seen.
For each node, we check if its complement (i.e., target - current node's value) exists in the set:

  • If it does, we return True.
  • Otherwise, we add the current value to the set and continue traversing the tree.

Note: This approach does not utilize the unique inorder property of a Binary Search Tree (BST). It treats the input tree as a general binary tree.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
        seen = set()

        def dfs(node):
            if not node:
                return False
            if k - node.val in seen:
                return True
            seen.add(node.val)
            return dfs(node.left) or dfs(node.right)

        return dfs(root)

Complexity Analysis

Here, n is the number of nodes in the tree, and h is the height of the tree.

  • Time Complexity: O(n) – Each node is visited once during the DFS traversal.
  • Space Complexity: O(n)
    • HashSet Space: O(n) – In the worst case, up to n node values may be stored in the HashSet.
    • Recursion Stack Space: O(h) – The recursion stack may use up to O(h) space, and in the worst case (e.g., a skewed tree), h can be as large as O(n).

We perform a breadth-first search (BFS) — also known as level-order traversal of the tree while maintaining a HashSet of values we've already seen. For each node, we check if its complement (i.e., target - current node's value) exists in the set:

  • If it does, we return True.
  • Otherwise, we add the current value to the set and continue traversing the tree.

Note: This approach does not utilize the unique inorder property of a Binary Search Tree (BST). It treats the input tree as a general binary tree.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
        if not root:
            return False
        
        seen = set()
        queue = collections.deque([root])

        while queue:
            node = queue.popleft()
            if k - node.val in seen:
                return True
            seen.add(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        return False

Complexity Analysis

Here n is the number of nodes in the tree.

  • Time Complexity: O(n) – Each node is visited once during the BFS traversal.
  • Space Complexity: O(n) – In the worst case, up to n node values may be stored in the HashSet and the queue simultaneously.

Fact: Inorder traversal of a Binary Search Tree (BST) gives the node values in sorted order.

Approach: We first perform an inorder traversal on the BST, which gives us a sorted list of its node values. Next, we apply the two-pointer technique on the sorted list: one pointer starts at the beginning (smallest value), and the other at the end (largest value).

  • If the sum of the two values is less than k, we move the left pointer to the right to increase the sum, since the list is sorted.
  • If the sum is greater than k, we move the right pointer to the left to decrease the sum.

We repeat this until we either find two values that sum to k or the pointers cross, meaning no such pair exists.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
        sorted_values = []

        def inorder(node):
            if not node:
                return
            inorder(node.left)
            sorted_values.append(node.val)
            inorder(node.right)
        
        inorder(root)

        left, right = 0, len(sorted_values) - 1
        while left < right:
            two_sum = sorted_values[left] + sorted_values[right]
            if two_sum == k:
                return True
            elif two_sum < k:
                left += 1
            else:
                right -= 1
        return False

Complexity Analysis

Here, n is the number of nodes in the tree, and h is the height of the tree.

  • Time Complexity: O(n)
    • Each node is visited once during the inorder traversal, and its value is accessed once more during the two-pointer search.
  • Space Complexity: O(n)
    • We use O(n) space for storing the sorted list of numbers.
    • Additionaly the recursion stack may up to O(h) space — and in the worst case, h can be up to O(n) (e.g. in a skewed tree).