Categories
Uncategorized

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
Uncategorized

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
Uncategorized

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
        }
        set.add(root.val)
        return find(root.left) || find(root.right)
    }
};