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:

Image for post
Image for post
Image for post
Image for post
Image for post
Image for post
Image for post
Image for post
(photo taken from Leetcode: https://leetcode.com/problems/two-sum-iv-input-is-a-bst/)

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.

Image for post
Image for post

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:

Image for post
Image for post
  • Step#3: Ideas combined:

with above thoughts we can do some modifications to solve this problem:

Image for post
Image for post

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:

Image for post
Image for post

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:

Image for post
Image for post

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!

Written by

Life is beautiful!

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store