CommonAncestorSearch { public static TreeNode<Integer> searchCommonAncestor(TreeNode<Integer> root, TreeNode<Integer> p, TreeNode<Integer> q){ if(!isDescendant(root, p) || !isDescendant(root, q)){ return null; } if(root == q || root== q){ return root; } boolean is_p_on_left = isDescendant(root.left, p); boolean is_q_on_left = isDescendant(root.left, q); if(is_p_on_left != is_q_on_left){ return root; } TreeNode<Integer> treeSide = is_p_on_left?root.left:root.right; return searchCommonAncestor(treeSide, p, q); }  static TreeNode<Integer> searchCommonAncestor(TreeNode<Integer> root, TreeNode<Integer> p, TreeNode<Integer> q);  }
@Test public void searchCommonAncestorTest(){ Assert.assertEquals(node4, CommonAncestorSearch.searchCommonAncestor(root, node3, node5)); Assert.assertEquals(node6, CommonAncestorSearch.searchCommonAncestor(root, node3, node7)); Assert.assertEquals(root, CommonAncestorSearch.searchCommonAncestor(root, node5, node10)); Assert.assertEquals(node11, CommonAncestorSearch.searchCommonAncestor(root, node10, node12)); Assert.assertEquals(null, CommonAncestorSearch.searchCommonAncestor(node6, node3, node10)); Assert.assertEquals(null, CommonAncestorSearch.searchCommonAncestor(node6, root, node3)); }