Simplest mistake could be the deadliest... how my O(n) failed on TC31, with explanation


  • 1
    T

    So, I don't know if someone else out there is as confused as I was when he/she is stuck on test case 31. The code cruised over the first 30 out of 31 test cases and failed on this one. This was my code:

    public class Solution {
        TreeNode LCA;
        boolean found;
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            LCA = null;
            found = false;
            traverse(root, p, q);
            return LCA;
        }
        
        private boolean traverse(TreeNode root, TreeNode p, TreeNode q) {
            int counter = 0;
            if (root.left != null && traverse(root.left, p, q)) counter ++;
            if (found) return true;
            if (root.right != null && traverse(root.right, p, q)) counter ++;
            if (found) return true;
            if (counter >= 2) {
                LCA = root;
                found = true;
                return true;
            }
            if (root.val == p.val || root.val == q.val) counter ++;
            if (counter >= 2) {
                LCA = root;
                found = true;
                return true;
            }
            if (counter >= 1) return true;
            return false;
        }
    }
    

    To put it simple, my mistake was that I compared the values instead of the reference, and case 31 happens to have duplicate values.

    public class Solution {
        TreeNode LCA;
        boolean found;
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            LCA = null;
            found = false;
            traverse(root, p, q);
            return LCA;
        }
        
        private boolean traverse(TreeNode root, TreeNode p, TreeNode q) {
            int counter = 0;
            if (root.left != null && traverse(root.left, p, q)) counter ++;
            if (found) return true;
            if (root.right != null && traverse(root.right, p, q)) counter ++;
            if (found) return true;
            if (counter >= 2) {
                LCA = root;
                found = true;
                return true;
            }
            if (root == p || root == q) counter ++;                 // <=====changed here
            if (counter >= 2) {
                LCA = root;
                found = true;
                return true;
            }
            if (counter >= 1) return true;
            return false;
        }
    }
    

    The algorithm I used is pretty straightforward. If a node finds itself has both of the desired nodes as itself and/or it's children, store itself. The whole thing takes less or equal to one dfs pass. O(n) time complexity + O(1) space complexity. There we go.


  • 0
    V

    Same thing happened with me, I was too checking for values. but after i removed the check for values and checked for node references. it worked fine. Can u elaborate why it failed on values?


  • 0
    T

    Like I mentioned above, there are different nodes with the same value in TC30. With my implementation whenever the first pair finds their LCA (which in this case are not the same as the input), all the parent nodes just simply returns without looking further.

    That said, I think as long as we are looking for values and there happens to have duplicates, some error will always happen regardless of the specific implementation.


  • 0
    T

    Here's TC 30 for those wondering:

         37
       /     \
      /       \
    -34       -48
       \     /   \
     -100  -100  48
                 /
               -54
              /   \
            -71   -22
                    \
                     8

  • 0
    T

    I failed on the same thing. Mine returned the root when checking for values (correctly), but the problem says "given nodes".


  • 0
    T

    Thanks for posting this nice graph Rob. I was a little confused about it because I remember the one that I failed was a lot larger data set. Turned out that it's TC31 not TC30. Not sure how I made that mistake, or maybe OJ has shuffled the cases. Sorry about the confusion.


  • 0
    T

    Hmm, that's interesting because I made the same mistake of .val==.val and it choked on this. There isn't much confusion, while your algo may work on this (don't know how), it demonstrates nicely what you're talking about in your post.


  • 0
    T

    Did your code fail on TC 30? I think ideally it should not fail, since there are no nodes with duplicate val as the required nodes p and q. Is it possible that there is a different issue?


  • 0
    T

    "29 / 31 test cases passed." above tree serialized and p=-100 (in the right subtree), q=-71; expected=48, mine=37. I had .val comparison then I changed it to simple root == p and suddenly it worked :)


  • 0
    T

    Ugh, now I understand how mine worked on this one. In my implementation it is the lowest node that meets the criteria that's returned, which happened to be the case for -48 even with the val == val criteria. But since you must have a different implementation this happened not to be the case. Anyway both are correct with the correct reference == reference criteria. GJ!


  • 0
    T

    I had a similar issue, see discussion in question's comments:

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null; // leaf
        // TODO in the failed version this was: (root.val == p.val || root.val == q.val)
        if (root == p || root == q) return root; // found p or q
    
        // do we have p or q in the left or right subtree
        TreeNode left = root.left != null? lowestCommonAncestor(root.left, p, q) : null;
        TreeNode right = root.right != null? lowestCommonAncestor(root.right, p, q) : null;
    
        if (left != null && right != null) return root; // jackpot
        if (left != null) return left; // propagate up
        if (right != null) return right; // propagate up
        return null; // give up
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.