# My LeetCode Journey -- BST 4. Extra Problems

draft-post/TRANSFERRED-2019-12-28 Fang

## 1214. Two Sum BSTs

Given two binary search trees, return True if and only if there is a node in the first tree and a node in the second tree whose values sum up to a given integer target.

### Thought Process

If we collect both trees and save all values into two HashSet, the time cost is gonna be: `O(m + n + n*1) = O(m+2n)`, this seems okay but the memory cost is high `O(m + n)`.

If we’d like to utilize the BST property, space could be saved. We can iterate over one of the trees meanwhile do a binary search on the other tree for the complement value. This is going to cost `O(m * h)` or `O(m * logn)` time if n is balanced. Memory usage is cut down to the `O(h)` stacks used while descending down the tree. `h = height(tree1) > height(tree2) ? height(tree1) : height(tree2)`.

### My Solution

The solution below achieved 100% on both memory and runtime.

``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean twoSumBSTs(TreeNode root1, TreeNode root2, int target) {
if(root1 == null || root2 == null) return false;
if(search(root2, target - root1.val)) return true;

return twoSumBSTs(root1.left, root2, target) || twoSumBSTs(root1.right, root2, target);
}

/*
Time Cost: O(h)
Space cost: O(h) stacks
*/
public boolean search(TreeNode root2, int target){
if(root2 == null) return false;
if(root2.val == target) return true;
if(root2.val < target)
return search(root2.right, target);
else
return search(root2.left, target);
}
}``````

## 96. Unique Binary Search Trees

Given n, how many structurally unique BST’s (binary search trees) that store values 1 … n?

### Observations

• Once the root is decided, the range of each subtree is decided.
• Can use dynamic programming — subproblem structure is quite clear.

### My Solution

``````class Solution {

public int numTrees(int n) {
HashMap<Integer, Integer> map = memoize(n);

return map.get(n);
}

public HashMap<Integer, Integer> memoize(int n){
// build a map from tree size to number of unique trees, bottom-up
HashMap<Integer, Integer> map = new HashMap<>();
map.put(0, 1);
map.put(1, 1);

for(int m = 2; m <= n; m++){
int cnt = 0;
for(int i = 0; i < m; i++){
Pair p = split(i, m);
cnt += map.get(p.left) * map.get(p.right);
}
map.put(m, cnt);
}
return map;
}

public Pair split(int ind, int n){
// given index of the root, return sizes of the left subtree and the right subtree
return new Pair(ind, n - 1 - ind);
}

private class Pair{
int left;
int right;
Pair(int l, int r){
left = l;
right = r;
}
}
}``````

This solution is very slow though:

• Runtime: 1 ms, faster than 13.52% of Java online submissions for Unique Binary Search Trees.
• Memory Usage: 32.9 MB, less than 5.55% of Java online submissions for Unique Binary Search Trees.

### LeetCode Solution

``````public class Solution {
public int numTrees(int n) {
int[] G = new int[n + 1];
G = 1;
G = 1;

for (int i = 2; i <= n; ++i) {
for (int j = 1; j <= i; ++j) {
G[i] += G[j - 1] * G[i - j];
}
}
return G[n];
}
}``````

## 95. Unique Binary Search Trees II

Different from the previous problem, here you need to actually generate all these trees.

``````class Solution {
public LinkedList<TreeNode> generate_trees(int start, int end) {
if (start > end) {
return all_trees;
}

// pick up a root
for (int i = start; i <= end; i++) {
// all possible left subtrees if i is choosen to be a root
LinkedList<TreeNode> left_trees = generate_trees(start, i - 1);

// all possible right subtrees if i is choosen to be a root
LinkedList<TreeNode> right_trees = generate_trees(i + 1, end);

// connect left and right trees to the root i
for (TreeNode l : left_trees) {
for (TreeNode r : right_trees) {
TreeNode current_tree = new TreeNode(i);
current_tree.left = l;
current_tree.right = r;
}
}
}
return all_trees;
}

public List<TreeNode> generateTrees(int n) {
if (n == 0) {