CODEWITHSUNDEEP
java
Jiaming Li
Jiaming Li

Reputation: 227

Performance difference when inverting a binary tree

Now I have two solution. But I can't figure out why the first solution is faster than the second solution.

First solution

public class Solution {
  public TreeNode invertTree(TreeNode root) {
        if(root == null)
            return root;

        if(root.left==null && root.right==null)
            return root;

        TreeNode temp = null;
        root.left = invertTree(root.left);
        root.right =invertTree(root.right);
        temp = root.left;
        root.left = root.right;
        root.right = temp;
        return root;
    }
}

Second solution

public class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null)
            return null;

        if (root.left == null && root.right == null)
            return root;

        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
}

Upvotes: 4

Views: 67

Answers (1)

Zbynek Vyskovsky - kvr000
Zbynek Vyskovsky - kvr000

Reputation: 18845

It would be worth seeing real numbers. But if we talk about quite big trees, it could be because of caching:
In the first solution you read root.left and root.right, then do the inversion and at the end you again manipulate root.left and root.right.
In the second solution you swap root.left and root.right and then immediately do the inversion. So you avoid at least one cache-miss for each node. Actually even the instruction code may be one instruction shorter as it may reuse already read variable.

Upvotes: 3

Related Questions