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

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

8 thoughts on “Lowest Common Ancestor of a Binary Tree: Anyone know why my output is undefined?”

Leave a Comment