# Daily Archives: January 30, 2016

## Find LCA in Binary Tree, Find LCA in BST

I wrote finding lca long time ago. Today, I learned this more concise code for finding LCA in Binary Tree.

The idea is that if there is no p or q in bottom, return null. Or return p, q or root.

```public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == p || root == q || root == null) {
return root;
}
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left != null && right != null) {
return root;
}
if (left != null) {
return left;
}
return right;
}```

Check my code on github: link

Below is the finding LCA in BST.

```public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) {
return null;
}
int max = Math.max(p.val, q.val);
int min = Math.min(p.val, q.val);
if (root.val >= min && root.val <= max) {
return root;
}
return root.val > max ? lowestCommonAncestor(root.left, p, q) : lowestCommonAncestor(root.right, p, q);
}```

Check my code on github: link

## Different Ways to Add Parentheses

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, – and *.

Example 1
Input: “2-1-1”.

((2-1)-1) = 0
(2-(1-1)) = 2
Output: [0, 2]
Example 2
Input: “2*3-4*5”

(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10
Output: [-34, -14, -10, -10, 10]

Solution. For String input, go through each char. If a char is ‘+’, ‘-‘ or ‘*’, then we calculate left and right. Left and right will be both List. Calculate all element combination in both left and right, and put in result.

Check my code on github: link