Can anybody tell the time complexity and space complexity for recursive approach?

  • 0

    Is it O(n) for time and O(logn) for space?

  • 1

    There are N elements in the array. The recursive approach creates N nodes for the tree.

    Space N nodes for N elements - O(N)
    Time N calls for N nodes - O(N)

    Although the recursion branches out to left and right by the power of 2, at the end of computation, N nodes have to be made, thus N calls to the recursive method.

  • 0

    It's O(n) both in run time and space

    For run time, just consider how many times a particular number will be treated as a root->only once. So each number leads to a recursive call.

    For space, just follow up the run time, each number leads to a recursive call, each recursive call takes O(1) space, n recursive calls takes O(n) space.

Log in to reply

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