Lowest Common Ancestor of a Binary Search Tree Error


  • 0
    C

    Below is my code for LCA. I could not pass the test case with [6,2,8,0,4,7,9,null,null,3,5]. why expected is 4? Should not it be 2 ?

        if((root.val-p.val)*(root.val-q.val) <= 0)
    		return root;
    	if((root.val < p.val) && (root.val<q.val))
    		return root;
    	
    	if(p.val < root.val && q.val < root.val)
    		return lowestCommonAncestor(root.left, p, q);
    	else
    		return lowestCommonAncestor(root.right, p, q);
    

    Input:
    [6,2,8,0,4,7,9,null,null,3,5], node with value 3, node with value 5
    Output:
    2
    Expected:
    4


  • 1

    Below is the binary tree representation of input: [6,2,8,0,4,7,9,null,null,3,5].

            _______6______
           /              \
        ___2__          ___8__
       /      \        /      \
       0      _4       7       9
             /  \
             3   5
    

    As you can see, when p = 3, and q = 5, their LCA is node with value 4. Although node with value 2 is also a common ancestor of p and q, it is not the lowest.


  • 0
    C

    here lower means value or the place in tree ? I thought it was the value.


  • 0

    Lower means the node that is located lower in the tree.


  • 0
    C

    ok, thank you.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.