Question

0

191

Views

Trying to solve Lowest common ancestor

var lowestCommonAncestor = function(root, p, q) {
  // return the path to the node
  let path = []
  const search = (node, target) => {
    if (node === null) return false
    
    path.push(node)
    
    if (node === target) return true
    
    const leftSearched = search(node.left, target)
    
    if (leftSearched) return true
    
    const rightSearched = search(node.right,target)
    
    if (rightSearched) return true
    
    path.pop()
  }
  
  search(root, p)
  const pathP = path
  path = []
  search(root, q)
  const pathQ = path
  
  let result
  while(pathP.length > 0 && pathQ.length > 0 && pathP[0] === pathQ[0]) {
    result = pathP[0]
    pathP.shift()
    pathQ.shift()
  }

  return result
};


console.log(lowestCommonAncestor([3,5,1,6,2,0,8,null,null,7,4],5,1));

Iam getting following error message const leftSearched = search(node.left, target) ^ TypeError: Cannot read property 'left' of undefined

Could someone help me to fix this issue

about 4 years ago · Juan Pablo Isaza

1 answers

Answer question

0

Answer question

Find remote jobs

Accepted Answer · 2022-07-04T12:58:03.979Z

Leet Code, as some other code challenge sites, will transform the array input (actually the text input having JSON notation) into an instance of TreeNode, and will pass that as argument to the function with your solution code.

When you want to run the solution locally, you'll have to take care of this transformation yourself. For that purpose you could make use of the fromList function -- specifically for binary trees.

NB: you have a bug in your search function. if (node === target) should be if (node.val === target).

// LeetCode template:
function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}

// Tool to convert array input to a tree: 
function fromList(values) {
    if (!values) return;

    let it = (function* () {
        for (let value of values) {
            yield value == null ? null : new TreeNode(value);
        }
        while (true) yield null;
    })();
        
    let root = it.next().value;
    let nextlevel = [root];
    while (nextlevel.length) {
        let level = nextlevel;
        nextlevel = [];
        for (let node of level) {
            if (node) {
                node.left = it.next().value;
                node.right = it.next().value;
                nextlevel.push(node.left, node.right);
            }
        }
    }
    return root;
}

// Your function
var lowestCommonAncestor = function(root, p, q) {
  // return the path to the node
  let path = []
  const search = (node, target) => {
    if (node === null) return false;
    path.push(node);
    if (node.val === target) return true;
    const leftSearched = search(node.left, target);
    if (leftSearched) return true;
    const rightSearched = search(node.right,target);
    if (rightSearched) return true;
    path.pop();
  }
  
  search(root, p);
  const pathP = path;
  path = [];
  search(root, q);
  const pathQ = path;
  
  let result;
  while(pathP.length > 0 && pathQ.length > 0 && pathP[0] === pathQ[0]) {
    result = pathP[0];
    pathP.shift();
    pathQ.shift();
  }

  return result;
};

// Running your solution on some input
let input = [3,5,1,6,2,0,8,null,null,7,4];
// Make the conversion that LeetCode would do
let root = fromList(input);
let lca = lowestCommonAncestor(root,5,1);
// For your own purposes, just print the value of that node:
console.log(lca.val); // 3

0

191

Trying to solve Lowest common ancestor

1 answers

0

Find remote jobs

Andres GPT