Crack Leetcode 653: Two Sum IV — Input is a BST
There is a way to make it easy.
Sometimes they make it look hard, while in fact, there’s always a way you can easily understand. Today, we’ll crack leetcode 653 —Two Sum IV: Input is a BST — together. Without further ado, let’s get started.
Problem Description:
Solution:
Ideation:
If the input is not a tree, but merely a list, then we can use the TwoSum method#2(one pass) I wrote about earlier.
- Step#1: Recall Leetcode Problem 1-- Two Sum:
As a quick refresher, basically the idea is to traverse the list for once, during which we build a dictionary for the numbers in input list. The numbers acts as key, and in that problem we are required to return the index, so we used index as its value.
The trick is to query whether (target-number) is in the “under-construction” dictionary when traversing the list. If it already exist, then we return, and no need to keep building the dictionary. Otherwise we keep building.
- Step#2: Adapt to this problem:
The only difference here is that the input here is a Binary Search Tree. If we know how to traverse a tree, then we can use the exact same method as above.
— — Traverse a tree:
We can use recursion to traverse a tree:
- Step#3: Ideas combined:
with above thoughts we can do some modifications to solve this problem:
Note: this problem only requires to return True or False, meaning found two node values that sum up to target or not. So for the dictionary key-value pair, the value doesn’t matter, for example we can say value = 1.
Python Code:
Complexity Analysis:
Time Complexity:
- Best-Case:
Best Case Time Complexity is that the first number it finds is the right pair for root. Therefore, best-case time complexity = O(1).
- Worst-Case:
Worst Case Time Complexity is when it needs to go over the whole tree to find the answer. Therefore, worst-case time complexity = O(N), where N is total number of nodes in the tree.
- Average-Case:
Average Case calculation is to sum up all the expectations of possible cases. So the sum is like this:
and the sum = (N+1)/3. Therefore the average case time complexity = O(N).
Space Complexity:
The maximum auxiliary space it takes is when the dictionary stores all the nodes in the tree. Therefore the auxiliary Space Complexity = O(N), where N is the total number of nodes in the tree.
The End:
Thanks for reading! Please check our articles more often, if you’d like to support our work — and we’ll see you in the next one!
