653. Two Sum IV - Input is a BST

EasyTreeDepth-First SearchBreadth-First SearchBinary Search TreeHash TableTwo PointersBinary Tree
Leetcode Link

Problem Description

The problem presents a Binary Search Tree (BST) and an integer k. The goal is to determine if there are any two distinct elements within the BST that add up to k. The BST is a tree structure where the value of each node is greater than all the values in its left subtree and less than all the values in its right subtree. This special property will play a key role in solving the problem efficiently. The solution should return true if such a pair exists or false otherwise.

Intuition

The intuition behind the solution comes from the properties of a BST. In a sorted array, a common approach to find if two numbers sum up to k is to use two pointers, one starting from the beginning and one from the end, moving towards each other until they find a pair that adds up to k or until they meet. We can use a similar approach with a BST using an inorder traversal, which will give us the elements in sorted order.

However, instead of using two pointers, we can use a HashSet (vis in the provided code) to store the values we've seen so far as we traverse the tree. While traversing, for each node with value val, we check if k - val is in our HashSet. If it is, we've found a pair that adds up to k and we can return true. If not, we add val to the HashSet and keep traversing. This approach leverages the BST property to eliminate the necessity of having the sorted list beforehand, and the HashSet to check for the complement in O(1) average time complexity, leading to an efficient overall solution.

The provided solution uses Depth-First Search (DFS) to traverse the BST. The recursive dfs function checks if the current node is None and, if not, proceeds to do the following:

  1. Check if the complement of the current node's value (i.e., k - root.val) exists in the visited HashSet.
  2. If the complement exists, return true as we found a valid pair.
  3. If the complement does not exist, add the current node's value to the HashSet.
  4. Recursively apply the same logic to the left and right children of the current node, returning true if either call finds a valid pair.

This solution effectively traverses the BST once, resulting in a time complexity of O(n) where n is the number of nodes in the BST, and a space complexity of O(n) for the storage in the HashSet.

Learn more about Tree, Depth-First Search, Breadth-First Search, Binary Search Tree, Two Pointers and Binary Tree patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

Which data structure is used in a depth first search?

Solution Approach

The solution implements a Depth-First Search (DFS) to traverse through the nodes of the Binary Search Tree. The DFS pattern is chosen because it allows us to systematically visit and check every node in the BST for the conditions stipulated in the problem. Let's walk through the implementation step by step:

  • A helper function named dfs is defined, which is recursively called on each node in the tree. The purpose of this function is to both perform the search and to propagate the result of the search back up the call stack.
  • Inside the dfs function, we first check if the current node, referred to as root, is None. If it is, it means we have reached the end of a branch, and we return False because we cannot find a pair in a nonexistent (null) sub-tree.
1if root is None:
2    return False
  • Next, we check if the difference between k and the value of the current node root.val is in the set vis. If the difference is found, that means there is a value we have already visited in the tree that pairs with the current node's value to sum up to k. We then return True as we have found a valid pair.
1if k - root.val in vis:
2    return True
  • If we haven't found a valid pair yet, we add the value of the current node to the vis set to keep a record of it. This is because it could potentially be a complement to a node we visit later in the traversal.
1vis.add(root.val)
  • Finally, we need to continue the traversal on both the left and right subtrees. We recursively call the dfs function on root.left and root.right. We leverage the or operator to propagate a True result back up if either of the recursive calls finds a valid pair.
1return dfs(root.left) or dfs(root.right)

  • The vis set is a crucial data structure utilized in this approach. Its main purpose is to keep track of all the values we have seen in the BST during the traversal. The set is chosen because it provides an average-time complexity of O(1) for both insertions and lookups, making our checks for the complement efficient.

  • The dfs function is then called from within the findTarget function, which initializes the vis set and starts the process. The search is kicked off at the root of the tree.

1vis = set()
2return dfs(root)

By using the DFS traversal coupled with a set to record visited values, we efficiently search the BST for a pair of values that sum up to k. This approach effectively uses properties of the data structure (BST), an algorithm (DFS), and a pattern (using a set to track complement values) to solve the problem in O(n) time complexity, where n is the number of nodes in the tree, while maintaining O(n) space complexity for the set.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following uses divide and conquer strategy?

Example Walkthrough

Let's consider a small example to illustrate the solution approach. Assume we have a Binary Search Tree (BST) with the following structure:

1    5
2   / \
3  3   6
4 / \
52   4

And let's say we want to find if there are any two numbers within this BST that add up to k = 9.

Now, we will walk through the solution using the Depth-First Search (DFS) traversal and HashSet as described:

  1. We start the DFS with the root of the BST, which is the node with value 5. We initialize an empty HashSet vis to keep track of the values we've encountered.

  2. Since root is not None, we check if k - root.val (which is 9 - 5 = 4) is present in vis. It is not, so we proceed to add 5 to vis.

  3. Now we apply DFS to the left child of 5, which has the value 3.

  4. Again, we check if k - 3 = 6 is in vis. It is not, so we add 3 to vis.

  5. Next, we traverse to the left child of 3, which has the value 2. We check if k - 2 = 7 is in vis. It is not, we add 2 to vis.

  6. Since the node with value 2 has no children, we backtrack and apply DFS to the right child of 3, which is 4. Checking if k - 4 = 5 is in vis and we find that it is, meaning we have discovered a valid pair (4 and 5) which adds up to k = 9.

  7. Since we have found a valid pair, the function would return True immediately without continuing to traverse the rest of the tree.

Using this method, our search was efficient since we leveraged the BST's structure and avoided checking every possible combination of nodes. The HashSet allowed us to quickly assess whether the complement to the current node's value had already been visited. By using a recursive DFS approach, we were able to keep the implementation clear and systematic.

Solution Implementation

1class TreeNode:
2    # Definition for a binary tree node.
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left  # Reference to the left child node
6        self.right = right  # Reference to the right child node
7
8class Solution:
9    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
10        """
11        Determines if there are two elements in the BST such that their sum is equal to a given target.
12
13        :param root: Root node of the binary search tree
14        :param k: Target sum we want to find
15        :return: True if such a pair is found, False otherwise
16        """
17
18        # Helper function to perform a depth-first search
19        def depth_first_search(node):
20            # Base case: if the node is None, return False
21            if node is None:
22                return False
23            # If the complement of the current node's value (k - node.val) is in the visited set,
24            # we've found a pair that sums up to k.
25            if k - node.val in visited:
26                return True
27            # Add the current node's value to the visited set
28            visited.add(node.val)
29            # Recursively search the left and right subtrees
30            return depth_first_search(node.left) or depth_first_search(node.right)
31
32        visited = set()  # Initialize an empty set to store visited node values
33        return depth_first_search(root)  # Begin DFS with the root node
34
1// Definition for a binary tree node.
2class TreeNode {
3    int val;
4    TreeNode left;
5    TreeNode right;
6    TreeNode() {} // Default constructor
7    TreeNode(int val) { this.val = val; } // Constructor with node value
8    TreeNode(int val, TreeNode left, TreeNode right) { // Constructor with node value and children
9        this.val = val;
10        this.left = left;
11        this.right = right;
12    }
13}
14
15class Solution {
16    // A HashSet to keep track of the values we've visited
17    private Set<Integer> visited = new HashSet<>();
18    private int targetSum;
19
20    // Public method to find if the tree has two elements such that their sum equals k
21    public boolean findTarget(TreeNode root, int k) {
22        this.targetSum = k;
23        return dfs(root);
24    }
25
26    // Helper method that uses depth-first search to find if the property is satisfied
27    private boolean dfs(TreeNode node) {
28        if (node == null) {
29            return false; // Base case: if the node is null, return false
30        }
31        if (visited.contains(targetSum - node.val)) {
32            // If the complementary value is in 'visited', we found two numbers that add up to 'k'
33            return true;
34        }
35        visited.add(node.val); // Add current node's value to the set
36        // Recurse on left and right subtrees; return true if any subtree returns true
37        return dfs(node.left) || dfs(node.right);
38    }
39}
40
1#include <unordered_set>
2#include <functional>
3
4// Definition for a binary tree node.
5struct TreeNode {
6    int val;
7    TreeNode *left;
8    TreeNode *right;
9    TreeNode() : val(0), left(nullptr), right(nullptr) {}
10    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
11    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
12};
13
14class Solution {
15public:
16    // Function to check if there exists two elements in the BST such that their sum is equal to the given value 'k'.
17    bool findTarget(TreeNode* root, int k) {
18        // Using an unordered set to store the values we've visited.
19        std::unordered_set<int> visited;
20
21        // Lambda function to perform Depth-First Search (DFS) on the binary tree.
22        std::function<bool(TreeNode*)> dfs = [&](TreeNode* node) {
23            // Base case: if the current node is null, we return false as we haven't found the pair.
24            if (!node) {
25                return false;
26            }
27            // If the complement of the current node's value (k - node's value) has already been visited, we've found a pair.
28            if (visited.count(k - node->val)) {
29                return true;
30            }
31            // Insert the current node's value into the visited set.
32            visited.insert(node->val);
33            // Continue the search on the left and right subtree.
34            return dfs(node->left) || dfs(node->right);
35        };
36
37        // Start DFS from the root of the binary tree.
38        return dfs(root);
39    }
40};
41
1/**
2 * Definition for a binary tree node.
3 */
4class TreeNode {
5    val: number
6    left: TreeNode | null
7    right: TreeNode | null
8
9    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
10        this.val = (val === undefined ? 0 : val)
11        this.left = (left === undefined ? null : left)
12        this.right = (right === undefined ? null : right)
13    }
14}
15
16/**
17 * Find if there exists any pair of nodes such that their sum equals k.
18 * 
19 * @param {TreeNode | null} root - The root of the binary tree.
20 * @param {number} k - The sum that we need to find.
21 * @returns {boolean} - True if such a pair is found, else false.
22 */
23function findTarget(root: TreeNode | null, k: number): boolean {
24    // Function to perform the depth-first search
25    const depthFirstSearch = (node: TreeNode | null): boolean => {
26        // If the node is null, return false.
27        if (!node) {
28            return false;
29        }
30        // If the complement of current node's value is seen before, return true.
31        if (visitedValues.has(k - node.val)) {
32            return true;
33        }
34        // Add the current node's value into the set.
35        visitedValues.add(node.val);
36        // Recur for left and right children.
37        return depthFirstSearch(node.left) || depthFirstSearch(node.right);
38    };
39
40    // Set to store visited nodes values
41    const visitedValues = new Set<number>();
42
43    // Initiating the depth-first search
44    return depthFirstSearch(root);
45}
46
Not Sure What to Study? Take the 2-min Quiz๏ผš

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Time and Space Complexity

The given Python code is aimed at determining whether there are two nodes in a binary tree that add up to a given sum k. To achieve this, it performs a Depth-First Search (DFS) and uses a set vis to record the values it has encountered.

Here's the computational complexity breakdown:

Time complexity

The DFS traverses each node exactly once, irrespective of the tree structure, because we are looking at each value only once and checking if its complementary (k - root.val) is in the vis set.

Therefore, the time complexity is O(n), where n is the number of nodes in the binary tree.

Space complexity

The space complexity consists of two main components:

  1. The space used by the vis set: In the worst case, it might store all the values contained in the tree, so it would be O(n).

  2. The space used by the call stack during the DFS: In the worst-case scenario of a completely unbalanced tree (where each node has only one child), the call stack would grow as large as the height of the tree, which would be O(n).

Considering both components, the overall space complexity of the algorithm is O(n), with n being the number of nodes in the tree.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

Recommended Readings

Everything About Trees

Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

BFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ