Sunday, November 16, 2014

Facebook: LCA without parent pointer

LCA problem with no parent pointers. Given the root of a tree and pointers to two nodes contained in that tree, return the lowest common ancestor of the two nodes. IE, the common ancestor furthest from the root. 


1. What if we could get the parent of each node in the binary tree? i.e, the structure of the tree contains a parent node? 
Then the answer could be quite easy.
The solution comes from Nine chapter: 
http://www.ninechapter.com/solutions/lowest-common-ancestor/

Code (Java):
Version 1: Traditional Method

public class Solution {
    private ArrayList<TreeNode> getPath2Root(TreeNode node) {
        ArrayList<TreeNode> list = new ArrayList<TreeNode>();
        while (node != null) {
            list.add(node);
            node = node.parent;
        }
        return list;
    }
    public TreeNode lowestCommonAncestor(TreeNode node1, TreeNode node2) {
        ArrayList<TreeNode> list1 = getPath2Root(node1);
        ArrayList<TreeNode> list2 = getPath2Root(node2);
        
        int i, j;
        for (i = list1.size() - 1, j = list2.size() - 1; i >= 0 && j >= 0; i--, j--) {
            if (list1.get(i) != list2.get(j)) {
                return list1.get(i).parent;
            }
        }
        return list1.get(i+1);
    }
}

Version 2: Divide & Conquer

public class Solution {
    private TreeNode getRoot(node) {
        while (node.parent != null) {
            node = node.parent;
        }
        return node;
    }
    
    private TreeNode getAncestor(TreeNode root, TreeNode node1, TreeNode node2) {
        if (root == null || root == node1 || root == node2) {
            return root;
        }
        
        // Divide
        TreeNode left = getAncestor(root.left, node1, node2);
        TreeNode right = getAncestor(root.right, node1, node2);
        
        // Conquer
        if (left != null && right != null) {
            return root;
        } 
        if (left != null) {
            return left;
        }
        if (right != null) {
            return right;
        }
        return null;
    }
    
    public TreeNode lowestCommonAncestor(TreeNode node1, TreeNode node2) {
        if (node1 == null || node2 == null) {
            return null;
        }
        TreeNode root = getRoot(node1);
        return getAncestor(root, node1, node2);
    }
}

Now let's consider the solution that we cannot consider the parent node.
Naive Solution:
Find the path of node1 and node2, compare the elements of the path. When the first time they are different, return the element before it. 

Code (Java):
import java.util.*;

class TreeNode {
  int val;
  TreeNode left;
  TreeNode right;
  TreeNode (int x) { val = x; }
}

public class LCA {
  public TreeNode lowestCommonAncestor(TreeNode root, TreeNode node1, TreeNode node2) {
    List<TreeNode> path1 = new ArrayList<TreeNode>();
    List<TreeNode> path2 = new ArrayList<TreeNode>();
    if (root == null || node1 == null || node2 == null) {
      return null;
    }

    if (findPath(root, node1, path1) == false || findPath(root, node2, path2) == false) {
      return null;
    }

    int i, j;
    for (i = 0, j = 0; i < path1.size() && j < path2.size(); i++, j++) {
      if (path1.get(i).val != path2.get(j).val) {
        return path1.get(i - 1);
      }
    }
    return path1.get(i - 1);
  }

  private boolean findPath(TreeNode root, TreeNode node, List<TreeNode> path) {
    if (root == null) {
      return false;
    }
    
    path.add(root);

    if (root.val == node.val) {
      return true;
    }

    if ((root.left != null && findPath(root.left, node, path)) || 
        (root.right != null && findPath(root.right, node, path))) {
      return true;
    }
    
    path.remove(path.size() - 1);
    return false;
  }

  public static void main(String[] args) {
    LCA sol = new LCA();

    TreeNode root = new TreeNode(20);
    root.left = new TreeNode(8);
    root.right = new TreeNode(22);

    root.left.left = new TreeNode(4);
    root.left.right = new TreeNode(12);
    root.left.right.left = new TreeNode(10);
    root.left.right.right = new TreeNode(14);

    TreeNode ans = sol.lowestCommonAncestor(root, root.left.left, root);

    System.out.println(ans.val);
  }
}

Discussion:
Time complexity of LCA of binary tree is O(n). That is because we traverse the tree in DFS order and delete the unrelated numbers. So the time complexity is still O(n) not O(h). The space complexity of this solution is O(n) as well. Do be careful the time complexity of LCA for BST, which is O(h).

A better Solution:
A better solution could use Divide and Conquer solution.


public class LCA {
  public TreeNode lowestCommonAncestor(TreeNode root, TreeNode node1, TreeNode node2) {
    if (root == null || root == node1 || root == node2) {
      return root;
    }

    // Divide
    TreeNode left = lowestCommonAncestor(root.left, node1, node2);
    TreeNode right = lowestCommonAncestor(root.right, node1, node2);

    // Conquer
    if (left != null && right != null) {
      return root;
    }

    if (left != null) {
      return left;
    }

    if (right != null) {
      return right;
    }

    return null;
  }

No comments:

Post a Comment