[LeetCode] Two Sum IV - Input is a BST

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

Example:

Input: root = [5,3,6,2,4,null,7], k = 9
Output: true

Input: root = [5,3,6,2,4,null,7], k = 28
Output: false

Input: root = [2,1,3], k = 4
Output: true

Input: root = [2,1,3], k = 1
Output: false

Input: root = [2,1,3], k = 3
Output: true

Approach: There are multiple approaches we can take here to solve this problem. One of simplest approach would be to take one node of binary search tree and then search for k - node.val in the input binary search tree. Here is how the approach looks like:

• DEF DoesSumExist(root, node, k):
• IF node == NULL
• RETURN FALSE
• IF (DoesElementExist(root , k - node.val))
• RETURN TRUE
• RETURN DoesSumExist(root, node.left, k) OR DoesSumExist(root, node.right, k)

• DEF DoesElementExist(node, val):
• WHILE node ! = null
• IF node.val == val
• RETURN TRUE
• ELSE IF node.val < val
• node = node.right
• ELSE
• node = node.left
• RETURN FALSE

The above approach will work but this approach will take O(nlogn) time. Let's try to optimize it. What we can do is we can store this BSTree in an array using inorder traversal. This will make sure the array is sorted. Now we can use two pointer approach to find the two elements whose sum is equal to k. Here is the algorithm:

• DEF DoesSumExist(root, k)
• sortedArray = []
• PutElementsInSortedArray(root, sortedArray)
• RETURN DoesSumExistInSortedArray(sortedArray, k)

• DEF PutElementsInSortedArray(node, sortedArray)
• IF node != null
• PutElementsInSortedArray(node.left, sortedArray)
• sortedArray.Add(node.val)
• PutElementsInSortedArray(node.right, sortedArray)

• DEF DoesSumExistInSortedArray(sortedArray, k)
• start = 0, end = Length(sortedArray) - 1
• WHILE start < end
• sum = sortedArray[start] + sortedArray[end]
• IF sum == k
• RETURN TRUE
• ELSE sum < k
• start = start + 1
• ELSE
• end = end - 1
• RETURN FALSE

The above approach will solve the problem in linear time which is definitely a considerable improvement but if you see we are traversing the same elements twice (once in tree and once in array) and also we are taking O(n) space every time. Let's try to do better!

We can use hashing here to solve this problem efficiently. We can use any traversal and we keep putting the values(node.val) in the hash set. Now at any time if we find k - node.val in hash set we can return true immediately otherwise we keep on traversing the tree. Here is the algorithm of this approach:

• DEF DoesSumExist(root, k):
• hashSet = []
• RETURN DoesSumExistUsingSet(root, k, hashSet)

• DEF DoesSumExistUsingSet(node, k, hashSet):
• IF node == null
• RETURN FALSE
• IF hashSet has (k - node.val)
• RETURN TRUE
• hashSet.Add(node.val)
• RETURN DoesSumExistUsingSet(node.left, k hashSet) OR DoesSumExistUsingSet(node.right, k, hashSet)

You can see we are just traversing tree once in this approach and also the extra space could be less than number of elements in the tree. However HashSet could take more space than an array or list.

I am giving the implementation of Approach 2 and Approach 3.

Implementation in C#:

Approach 2: Flatten the BSTree to Sorted Array:

    public bool FindTarget(TreeNode root, int k) 

    {

        List<int> flattenBSTreeList = new List<int>();

        this.FlattenBSTree(root, flattenBSTreeList);

        return this.IsSumExist(flattenBSTreeList, k);

    }

    

    private void FlattenBSTree(TreeNode node, List<int> flattenBSTreeList)

    {

        if (node != null)

        {

            this.FlattenBSTree(node.left, flattenBSTreeList);

            flattenBSTreeList.Add(node.val);

            this.FlattenBSTree(node.right, flattenBSTreeList);

        }

    }

    private bool IsSumExist(List<int> flattenBSTreeList, int k)

    {

        int start = 0, end = flattenBSTreeList.Count - 1;

        while (start < end)

        {

            int currSum = flattenBSTreeList[start] + flattenBSTreeList[end];

            if (currSum == k)

            {

                return true;

            }

            else if (currSum < k)

            {

                ++start;

            }

            else

            {

                --end;

            }

        }

        return false;

    }

Approach 3: Using Hashing:

    public bool FindTarget(TreeNode root, int k) 

    {    

        HashSet<int> nodeValSet = new HashSet<int>();

        return this.IsSumExist(root, nodeValSet, k);

    }

    

    private bool IsSumExist(TreeNode node, HashSet<int> nodeValSet, int k)

    {

        if (node == null)

        {

            return false;

        }        

        if (nodeValSet.Contains(k - node.val))

        {

            return true;

        }

        nodeValSet.Add(node.val);        

        return this.IsSumExist(node.left, nodeValSet, k) || 

            this.IsSumExist(node.right, nodeValSet, k);

    }

Complexity: O(n) but preferred is approach 3 as it does only one traversal.