Lowest Common Ancestor of a Binary Tree: Anyone know why my output is undefined?

Question

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.

My code is running as expected. I used a hashMap to keep track of parent nodes as I traversed the tree. Then in a while loop, I push the parent nodes of the particular path I took to reach my p and q input nodes. In my for loop, I'm iterating through a path of parents and checking if that parent is in the second path. The first parent match is the LCA. The problem is my output is always undefined. My if condition in the for the loop is being met and I am printing the variable num correctly. Next line is a return for that num. However my output is still undefined. I can return anything from True, "string", etc. and my output doesnt change from undefined. Any insight to this issue is appreciated.

var lowestCommonAncestor = function(root, p, q) {
    let stack = [root] 
    let hash = new Map()
    
    while (stack.length) {
        let node = stack.pop() 
       
        
        if (node.right) {
            hash[node.right.val] = node.val
            stack.push(node.right)
        }
        
        if (node.left) {
            hash[node.left.val] = node.val
            stack.push(node.left)
        }
    }

    
    let path1 = [q.val, hash[q.val]]
    let path2 = [p.val, hash[p.val]]
   
    while (path1[path1.length - 1] !== root.val) { 
        path1.push(hash[path1[path1.length - 1]])
    }
    
     while (path2[path2.length - 1] !== root.val) {
        path2.push(hash[path2[path2.length - 1]])
    }
    
  
    for (let i = 0; i < path1.length; i ++) {
        let num = path1[i]
        if (path2.indexOf(num) !== -1) {
            console.log(num)
            return num
        }
        
    }
  
};

myinput: [3,5,1,6,2,0,8,null,null,7,4], 7, 8

stdout: 3 (correct)

output: undefined

Welcome to StackOverflow! Please edit the question to add a more complete description of the problem you're trying to solve, along with some sample data and the expected and actual outputs from that data. — Scott Sauyet
Hi Scott, thanks for the advice. I have edited the question to be as thorough as possible. :) — Daniel Lancaster

trincot trincot · Accepted Answer · 2021-02-18T20:47:37

The main problem is that you are asked to return the lowest common ancestor: this is not a value, but a node. So you should not return the val property, but the node object that has that property.

This really means that you should remove all references to val properties from your code: they are irrelevant.

There are two more issues in your code:

A Map object has set and get methods. You are instead creating string properties on that object. That works because you key by val, but after the above observation, you'll need to key by node object, and so you really need to use the Map.get and Map.set methods properly.
You initialise path1 and path2 with 2 values each. But that will give problems when one of the p or q arguments is the root itself. You should start path1 and path2 with just one element each. The loop will do the rest.

So here is your code corrected:

var lowestCommonAncestor = function(root, p, q) {
    let stack = [root];
    let hash = new Map();

    while (stack.length) {
        let node = stack.pop(); 

        if (node.right) {
            hash.set(node.right, node);
            stack.push(node.right);
        }

        if (node.left) {
            hash.set(node.left, node);
            stack.push(node.left);
        }
    }


    let path1 = [q];
    let path2 = [p];

    while (path1[path1.length - 1] !== root) { 
        path1.push(hash.get(path1[path1.length - 1]));
    }

    while (path2[path2.length - 1] !== root) {
        path2.push(hash.get(path2[path2.length - 1]));
    }

    for (let i = 0; i < path1.length; i ++) {
        let node = path1[i];
        if (path2.indexOf(node) !== -1) {
            return node;
        }
    }
}

NB: please use the habit of ending statements with a semicolon. There is really no good reason why you would leave that to the automatic semicolon insertion algorithm. You would not be the first to fall for one of the traps it has.

Lowest Common Ancestor of a Binary Tree: Anyone know why my output is undefined?

2 Answers