3 lines with O(1) space, 1-Liners, Alternatives


  • 267

    Just walk down from the whole tree's root as long as both p and q are in the same subtree (meaning their values are both smaller or both larger than root's). This walks straight from the root to the LCA, not looking at the rest of the tree, so it's pretty much as fast as it gets. A few ways to do it:

    Iterative, O(1) space

    Python

    def lowestCommonAncestor(self, root, p, q):
        while (root.val - p.val) * (root.val - q.val) > 0:
            root = (root.left, root.right)[p.val > root.val]
        return root
    

    Java

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while ((root.val - p.val) * (root.val - q.val) > 0)
            root = p.val < root.val ? root.left : root.right;
        return root;
    }
    

    (in case of overflow, I'd do (root.val - (long)p.val) * (root.val - (long)q.val))

    Different Python

    def lowestCommonAncestor(self, root, p, q):
        a, b = sorted([p.val, q.val])
        while not a <= root.val <= b:
            root = (root.left, root.right)[a > root.val]
        return root
    

    "Long" Python, maybe easiest to understand

    def lowestCommonAncestor(self, root, p, q):
        while root:
            if p.val < root.val > q.val:
                root = root.left
            elif p.val > root.val < q.val:
                root = root.right
            else:
                return root
    

    Recursive

    Python

    def lowestCommonAncestor(self, root, p, q):
        next = p.val < root.val > q.val and root.left or \
               p.val > root.val < q.val and root.right
        return self.lowestCommonAncestor(next, p, q) if next else root
    

    Python One-Liner

    def lowestCommonAncestor(self, root, p, q):
        return root if (root.val - p.val) * (root.val - q.val) < 1 else \
               self.lowestCommonAncestor((root.left, root.right)[p.val > root.val], p, q)
    

    Java One-Liner

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        return (root.val - p.val) * (root.val - q.val) < 1 ? root :
               lowestCommonAncestor(p.val < root.val ? root.left : root.right, p, q);
    }
    

    "Long" Python, maybe easiest to understand

    def lowestCommonAncestor(self, root, p, q):
        if p.val < root.val > q.val:
            return self.lowestCommonAncestor(root.left, p, q)
        if p.val > root.val < q.val:
            return self.lowestCommonAncestor(root.right, p, q)
        return root

  • 0
    H

    It might be better to add a line: " if not root: return None" as ‘NoneType' object has no attribute 'val'


  • 2

    Wow, I only come up with the idea present in your last "Long" Python code and have no idea of how to shorten it. There is always some surprise reading your codes.


  • 1

    @huyc Well, I just go with the requirements specified by the text and the test cases. Judging by all that, it looks like the problem author doesn't want us to have to deal with such cases here, so I don't.

    @jianchao.li.fighter Hehe :-) In real life, I think that "long" version or an iterative version of it would be best, as it's not really long, and clearer than the others. But I enjoyed playing with different things here.


  • 0

    @huyc and @jianchao.li.fighter I just did add an iterative version of that "long" solution, and instead of while True I use while root, which handles the case @huyc mentioned without adding a single extra byte to the code :-)


  • 0
    S
    This post is deleted!

  • 0

    In root? You mean in the tree? That doesn't need to be checked. The problem statement says:

    Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.


  • 3
    A

    I wonder if * costs more time.


  • 0
    L
    This post is deleted!

  • 0
    H

    Hi, could explain this code"root = (root.left, root.right)[p.val > root.val]" for me? thanks


  • 1

    @hpplayer That just sets root to its left or right child as needed. I put both children in a tuple and then select the appropriate one.


  • 0
    H

    Thanks for the reply, could you tell me what such format "()[]" called, or how can I search more information about it?


  • 1

    It's just a tuple and indexing it. Nothing special.


  • 0
    G

    Hi @StefanPochmann do we need to consider the situation when the nodes is not distinct? (when some nodes have same 'val')


  • 0

    @gooddaydiablo Depends on the definition of binary search tree. Not here, as leetcode apparently uses this definition consistently:
    https://leetcode.com/problems/validate-binary-search-tree/


  • 0

    elegant code! you might can add this to avoid scan whole tree sometime:
    //save time to scan the tree
    if(p.left==q||p.right==q)
    {
    return p;
    }
    else if(q.left==p||q.right==p)
    {
    return q;
    }
    else
    {
    //let the scan beginning...
    }


  • 1
    L

    In recursive solutions, why the product needs to be < 1 instead of < 0 ?


  • 0

    @benjamin21st
    Hint: There is no "< 0" anywhere.


  • 1
    L

    If I understood correctly, isn't the first occurrence of '< 0' the point where p and q are on different sides of 'root', and hence 'root' is the LowestCommonAncestor?


  • 0

    Not quite, no. It's enough if one of them is on a side of root that the other isn't on (the other can be root).


Log in to reply
 

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