Java/Python iterative solution


  • 110

    Python

    def lowestCommonAncestor(self, root, p, q):
        stack = [root]
        parent = {root: None}
        while p not in parent or q not in parent:
            node = stack.pop()
            if node.left:
                parent[node.left] = node
                stack.append(node.left)
            if node.right:
                parent[node.right] = node
                stack.append(node.right)
        ancestors = set()
        while p:
            ancestors.add(p)
            p = parent[p]
        while q not in ancestors:
            q = parent[q]
        return q
    
    # 31 / 31 test cases passed.
    # Status: Accepted
    # Runtime: 108 ms
    # 99.14%
    

    Java

    public class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            Map<TreeNode, TreeNode> parent = new HashMap<>();
            Deque<TreeNode> stack = new ArrayDeque<>();
            parent.put(root, null);
            stack.push(root);
    
            while (!parent.containsKey(p) || !parent.containsKey(q)) {
                TreeNode node = stack.pop();
                if (node.left != null) {
                    parent.put(node.left, node);
                    stack.push(node.left);
                }
                if (node.right != null) {
                    parent.put(node.right, node);
                    stack.push(node.right);
                }
            }
            Set<TreeNode> ancestors = new HashSet<>();
            while (p != null) {
                ancestors.add(p);
                p = parent.get(p);
            }
            while (!ancestors.contains(q))
                q = parent.get(q);
            return q;
        }
    }
    

    To find the lowest common ancestor, we need to find where is p and q and a way to track their ancestors. A parent pointer for each node found is good for the job. After we found both p and q, we create a set of p's ancestors. Then we travel through q's ancestors, the first one appears in p's is our answer.


  • 1
    X

    Very visual and clear!


  • 1
    F

    I like this, easy to understand. Thank you for sharing.


  • 2
    Z

    Good idea to build parent map, however when building the map, using a queue by level order is preferred.


  • 0

    Thank you pepsi! It is straightforward and fast!


  • 0
    C

    so cool!. learned


  • 1

    parent dictionary is a really good idea!


  • 0
    A

    @dietpepsi What is the running time for this solution?


  • 5
    A

    Another solution is to run DFS for both p and q values and create paths from root to p and q. These paths can be stored in lists. Since we need lowest common ancestor, we can check from the front for the last such node which is common in both the lists.

    Running time:
    DFS will lead to O(N) since this is a binary tree and not a binary search tree.
    Two DFS operations will lead to O(N)
    Comparison work of the lists - using a while loop - to find common element will take O(N)
    So total running time - O(N)

    Space
    Lists to store paths can lead to O(N)


  • 1
    S

    @acheiver Nice analysis. However, I think the worst case for DFS is O(n), where n is the node numbers in the tree. The average case is O(h).


  • 0
    A

    @sunraincyq Oh yes. You are right. The worst case for DFS is O(h) when the tree is a binary search tree not a binary tree. For a binary tree, it will be O(n)

    I have modified my statements.


  • 1
    X

    Easy to understand and implement. I convert your solution into C++ and post here for other's reference.

    class Solution {
    public:
        
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
            //iterative solution
            
            unordered_map<TreeNode*,TreeNode*> mm;
            mm[root]=NULL;
            queue<TreeNode*> qq;
            qq.push(root);
            while(mm.count(p)==0||mm.count(q)==0){
                TreeNode* tmp=qq.front();
                qq.pop();
                if(tmp->left){
                    mm[tmp->left]=tmp;
                    qq.push(tmp->left);
                }
                if(tmp->right){
                    mm[tmp->right]=tmp;
                    qq.push(tmp->right);
                }
            }
            unordered_set<TreeNode*> ss;
            while(p!=NULL){
                ss.insert(p);
                p=mm[p];
            }
            while(ss.count(q)==0){
                q=mm[q];
            }
            return q;
        }
    };

  • 0
    G
    This post is deleted!

  • 5
    G

    The idea is great, but I wonder why not use a queue to do BFS. If we use a stack it always traverses the right subtree first.

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        unordered_map<TreeNode*, TreeNode*> parents;
        parents[root] = nullptr;
        queue<TreeNode*> qu;
        qu.push(root);
        while (!parents.count(p) || !parents.count(q)) {
            int qsize = (int)qu.size();
            for (int i = 0; i < qsize; ++i) {
                auto node = qu.front();
                qu.pop();
                if (node -> left) {
                    parents[node -> left] = node;
                    qu.push(node -> left);
                }
                if (node -> right) {
                    parents[node -> right] = node;
                    qu.push(node -> right);
                }
            }
        }
        unordered_set<TreeNode*> ancestors;
        while (p) ancestors.insert(p), p = parents[p];
        while (q && !ancestors.count(q)) q = parents[q];
        return q;
    }
    

  • 0
    C

    excellent iterative solution...understood LCA concept through this code


  • 0
    K

    great and intuitive solution!


  • 0
    A

    This solution is wow..!!


  • 0
    M

    Easy to understand . Thank you !


  • 0
    S

    @garygao1993 I had the same question! Why not a queue?


  • 1

    @subbrammanian @garygao1993
    It doesn't really matter if we're using a stack or a queue. In this case, all we need is find p or q during the search, BFS just won't speed up it on average. Besides, writing stack only uses two characters [] while for queue in Python, you need collections.deque() which is much longer.


Log in to reply
 

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