CODEWITHSUNDEEP
recursiontime-complexitybinary-tree
fozzy_bear_waka_waka
fozzy_bear_waka_waka

Reputation: 87

Time Complexity for the given Tree Recursion problem

I was looking at the first Recursive solution for this problem on Leetcode. Here is the code for the proposed solution.

public boolean isSymmetric(TreeNode root) {
    return isMirror(root, root);
}

public boolean isMirror(TreeNode t1, TreeNode t2) {
    if (t1 == null && t2 == null) return true;
    if (t1 == null || t2 == null) return false;
    return (t1.val == t2.val)
        && isMirror(t1.right, t2.left)
        && isMirror(t1.left, t2.right);
}

The part of the solution that I do not understand is why the writer of the solution says the time complexity is O(n). Let's say I had the input:

   1
  / \
 2   2

This is how I trace the call stack in this case:

isMirror(1, 1)
    (t1.val == t2.val) returns true
    isMirror(2, 2) returns true
        (t1.val == t2.val) returns true
        isMirror(null, null) return true
        isMirror(null, null) return true
    isMirror(2, 2) returns true
        (t1.val == t2.val) returns true
        isMirror(null, null) return true
        isMirror(null, null) return true

In the call stack above, isMirror() is called 7 times while n is 3. For the time complexity to be O(n), should isMirror() have only been called 3 times? Or am I looking at this the wrong way? Is it the fact that the call stack only went 3 levels deep that shows that the time complexity is O(n)?

Thank you for the help.

Upvotes: 1

Views: 65

Answers (1)

kelalaka
kelalaka

Reputation: 5636

You call the mirror on the null nodes too. So your elements are actually not 3 they are 7. Think the next level on the binary tree and you will see.

Solutions;

  • Try to check the nullity before calling the function.
  • it will be still constant factor to your cost. Approximately 2 times. By big O rules you are still O(n).

Upvotes: 1

Related Questions