LowestCommonAncestorNoParent.java solution too complex

[ghost]

Hey all,

I noticed that the LowestCommonAncestorNoParent solution is a little more complex than it needs to be. The creation of a custom class to return values seems a little over the top, no?

What about this well known solution?

Pseudocode
If root null, return null
if root is one of the nodes, return root
recursively call lca on left and right
if both left and right not null, return root
if one of left and right is not null, return the non null node

Code

package EPIQuestions;

/**
 * Created by aalayo on 12/6/15.
 * Compute the lowest common ancestor in a binary tree
 *
 */
public class TenPointThree {
    private static class TreeNode {
        TreeNode l, r, p;
        int data;

        public TreeNode (int data) {this.data = data;}
    }

    private static TreeNode lca(TreeNode root, TreeNode n1, TreeNode n2) {
        if(root == null) return null;
        if(root == n1 || root == n2) return root;

        TreeNode l = lca(root.l, n1, n2);
        TreeNode r = lca(root.r, n1, n2);

        if(l != null && r != null) return root;
        return (l != null) ? l : r;
    }

    public static void test() {
        /*
                         314
                   6              6
              271     561      2     271
            28   0       3      1       28
        */
        // depth 0
        TreeNode h = new TreeNode(314);
        h.p = null;
        // depth 1
        h.l = new TreeNode(6);
        h.l.p = h;
        h.r = new TreeNode(6);
        h.r.p = h;
        // depth 2
        h.l.l = new TreeNode(271);
        h.l.l.p = h.l;
        h.l.r = new TreeNode(561);
        h.l.r.p = h.l;
        h.r.l = new TreeNode(2);
        h.r.l.p = h.r;
        h.r.r = new TreeNode(271);
        h.r.r.p = h.r;
        // depth 3
        h.l.l.l = new TreeNode(28);
        h.l.l.l.p = h.l.l;
        h.l.l.r = new TreeNode(0);
        h.l.l.r.p = h.l.l;
        h.l.r.r = new TreeNode(3);
        h.l.r.r.p = h.l.r;
        h.r.l.r = new TreeNode(1);
        h.r.l.r.p = h.r.l;
        h.r.r.r = new TreeNode(28);
        h.r.r.r.p = h.r.r;

        System.out.println("LCA without parent");

        TreeNode lcaNode = lca(h, h.l.l.l, h.r.r.r);
        System.out.println("lca of " + h.l.l.l.data +
                " and " + h.r.r.r.data + " is " + lcaNode.data);

        lcaNode = lca(h, h, h.r.r.r);
        System.out.println("lca of " + h.data +
                " and " + h.r.r.r.data + " is " + lcaNode.data);

        lcaNode = lca(h, h.l, h.l.r.r);
        System.out.println("lca of " + h.l.data +
                " and " + h.l.r.r.data + " is " + lcaNode.data);

        lcaNode = lca(h, h.l.l, h.l.r);
        System.out.println("lca of " + h.l.l.data +
                " and " + h.l.r.data + " is " + lcaNode.data);
    }
}

[skanagavelu]

Hi McFlurriez,

I think; the code is complex because of; when both nodes are found in left sub tree; the code will avoid traversing the right sub tree. This is not the case in your solution.

Thanks,
Kanagavelu Sugumar.

[ghost]

This is true. Perhaps there should be a note about different solutions in the next revision, as is the case with many solutions in the book?