| 10 | } |
| 11 | |
| 12 | public static TreeNode commonAncestorHelper(TreeNode root, TreeNode p, TreeNode q) { |
| 13 | if (root == null) { |
| 14 | return null; |
| 15 | } |
| 16 | boolean is_p_on_left = covers(root.left, p); |
| 17 | boolean is_q_on_left = covers(root.left, q); |
| 18 | if (is_p_on_left != is_q_on_left) { // Nodes are on different side |
| 19 | return root; |
| 20 | } |
| 21 | TreeNode child_side = is_p_on_left ? root.left : root.right; |
| 22 | return commonAncestorHelper(child_side, p, q); |
| 23 | } |
| 24 | |
| 25 | public static TreeNode commonAncestor(TreeNode root, TreeNode p, TreeNode q) { |
| 26 | if (!covers(root, p) || !covers(root, q)) { // Error check - one node is not in tree |