Categories

## 236. Lowest Common Ancestor of a Binary Tree Leetcode Javascript Solution

The Problem:

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Example 1:

```Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.
```

Example 2:

```Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.
```

Example 3:

```Input: root = [1,2], p = 1, q = 2
Output: 1
```

Constraints:

• The number of nodes in the tree is in the range `[2, 105]`.
• `-109 <= Node.val <= 109`
• All `Node.val` are unique.
• `p != q`
• `p` and `q` will exist in the tree.

The Solution:

```var lowestCommonAncestor = function(root, p, q) {
if(!root || root== p || root == q) return root
let left = lowestCommonAncestor(root.left,p,q)
let right = lowestCommonAncestor(root.right,p,q)
return (left && right) ? root : (left || right)
};```
Categories

## 106. Construct Binary Tree from Inorder and Postorder Traversal Leetcode Javascript Solution

The Problem:

Given two integer arrays `inorder` and `postorder` where `inorder` is the inorder traversal of a binary tree and `postorder` is the postorder traversal of the same tree, construct and return the binary tree.

Example 1:

```Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output: [3,9,20,null,null,15,7]
```

Example 2:

```Input: inorder = [-1], postorder = [-1]
Output: []
```

Constraints:

• `1 <= inorder.length <= 3000`
• `postorder.length == inorder.length`
• `-3000 <= inorder[i], postorder[i] <= 3000`
• `inorder` and `postorder` consist of unique values.
• Each value of `postorder` also appears in `inorder`.
• `inorder` is guaranteed to be the inorder traversal of the tree.
• `postorder` is guaranteed to be the postorder traversal of the tree.

The Solution:

I got stuck on this problem for days. Then after scrutinizing the code, I realized the problem lied in the condition in the if statement when I searched for the position of the root node in the inorder array recursively.

```var buildTree = function(inorder, postorder) {
function buildBT(postStart,postEnd,inStart, inEnd, inorder, postorder){
if( postStart > postEnd || inStart > inEnd){
return null;
}
let node = new TreeNode(postorder[postEnd])
if (inStart == inEnd || postStart == postEnd)
{return node;}
let position = 0, i = 0
while(i <= inEnd){
if(inorder[i] == node.val){
position = i
break
}
i++
}
/* console.log(position)
console.log("ps: " + postStart + " postend: " + postEnd + " inStart: " + inStart + " inEnd: " + inEnd) */
node.left = buildBT(postStart,postStart + position  - inStart-1 ,inStart, position-1, inorder, postorder)
node.right = buildBT( postEnd - inEnd + position,postEnd-1, position+1,inEnd, inorder, postorder)
return node
}
return buildBT(0,postorder.length-1,0, inorder.length-1, inorder, postorder)
};
```

Categories

## 653. Two Sum IV – Input is a BST Leetcode Javascript Solution

The 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 1:

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

Example 2:

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

Example 3:

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

Example 4:

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

Example 5:

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

Constraints:

• The number of nodes in the tree is in the range `[1, 104]`.
• `-104 <= Node.val <= 104`
• `root` is guaranteed to be a valid binary search tree.
• `-105 <= k <= 105`

The Solution:

We can use a HashSet to store the values seen so far while traversing the tree, when we see a new value, we check if the result of target – this number equals a number that is already in the set. If there exists such a number, we return true.

```var findTarget = function(root, k) {
let set = new Set()
return find(root)
function find(root){
if(!root){
return false;
}
if(set.has(k - root.val)){
return true
}