CODEWITHSUNDEEP
javarecursiontime-complexitybinary-treeinorder
sejo
sejo

Reputation: 17

How do I calculate time complexity and space complexity of this solution? Could you please explain it to me?

It is leetcode problem 94. Binary Tree inorder traversal.

       /**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
List<Integer> list = new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        if (root == null)
            return list;
        inorderTraversal(root.left);
        list.add(root.val);
        inorderTraversal(root.right);

        return list;
    }
}

I am not sure, but space complexity : O(1)? time complextity O(n)? because I am visiting each and every nodes at least once?

Usually what I do, if there's loop --> O(n), nested loop-->O(n^2), but I don't really sure how to calculate space complexity and time complexity in recursion. Could you help me with this concept please?

Thank you

Upvotes: 0

Views: 735

Answers (1)

trincot
trincot

Reputation: 350335

Time complexity

If we ignore the recursive calls, the time complexity for executing inOrderTraversal is θ(1): all the steps in the code, except the recursive calls, have Θ(1) complexity. Given that the graph is a tree, inOrderTraversal is called exactly once on each node, and on all null references. In a tree, the number of null references is equal to the number of nodes in the tree plus 1. So if the tree has 𝑛 nodes, the function is called 2𝑛+1 times. So the overal time complexity is Θ(2𝑛+1) = Θ(𝑛).

Space complexity

First, there is the space that is already occupied by the tree itself. This has Θ(𝑛) space complexity as there are 𝑛 TreeNode instances and one root reference variable. It is common to only look at the auxiliary time complexity, and then the space used by the input is ignored.

Then we have the space used by the output. We can consider as output the array in which node references will be stored: it has a constant overhead (like the size of the array) plus -- eventually -- 𝑛 node references, so this represents Θ(𝑛) space complexity. It is not uncommon to also exclude this from the space complexity, so check whether you need to include or exclude it.

The most interesting space complexity of an algorithm, concerns the temporary space it needs. Here we must consider the space used by the function call mechanism. Each execution context of the function uses a constant amount of space on the stack (for the stack frame, including the space for the parameter variable). When a function returns, this space is "freed" again as it can be used for a next call. The maximum stack space that is used during the process is Θ(ℎ+2) = Θ(ℎ), where ℎ is the height of the tree (i.e. the number of edges on longest path from root). Since the height of the tree is 𝑛−1 in the worst case (when the tree has just one leaf), this stack memory is bounded by O(𝑛). In the best case, the tree is completely balanced and then its height is Θ(log𝑛).

Concluding, we have these space complexities:

  • Input: Θ(𝑛)
  • Output: Θ(𝑛)
  • Auxiliary: worst case Θ(𝑛); best case Θ(log𝑛)
  • Auxiliary + output: Θ(𝑛)

So take your pick depending on what you want to consider for the space complexity.

Upvotes: 1

Related Questions