Posts Lowest Common Ancestor - Using In-time and Out-time
Post
Cancel

Lowest Common Ancestor - Using In-time and Out-time

PROBLEM DESCRIPTION

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).
leetcode

SOLUTION

snapshot

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Solution {
    
    Map<TreeNode, Integer> intime = new HashMap<>();
    Map<TreeNode, Integer> outtime = new HashMap<>();
    
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        
        //populate the in-time and out-time hash maps
        travel(root); 
                
        //start from root, which will be the ancestor of every node in the tree
        TreeNode current = root;
        
        while(current != null){

            //if the left node of current node is ancestor of both p and q, go left
            if(isAncestor(current.left, p) && isAncestor(current.left, q)){
                current = current.left;
            //if the right node of current node is ancestor of both p and q, go right
            }else if(isAncestor(current.right, p) && isAncestor(current.right, q)){
                current = current.right;
            //otherwise, current node must be the LCA
            }else{
                return current;
            }
        }
        
        return null;
        
    }
    
    int T = 0; 
    public void travel(TreeNode node){
        if(node == null) return;
        intime.put(node, T); T++;
        travel(node.left);
        travel(node.right);
        outtime.put(node, T); T++;
    }
    
    //Is A ancestor of B
    public boolean isAncestor(TreeNode A, TreeNode B){
        
        if(A == null || B == null) return false;
        
        int inA = intime.get(A);
        int inB = intime.get(B);
        int outA = outtime.get(A);
        int outB = outtime.get(B);
        
        //Main logic to check if A is an ancestor of B
        if(inA <= inB && outA >= outB){
            return true;
        }
        
        return false;
    }
}
This post is licensed under CC BY 4.0 by the author.