Can someone do this in place with O(n) time?


  • 2
    I

    I used an extra array to do this, it has O(n) storage and time.
    But I have a feeling that this one can be solved with O(1) memory, of course, linear time.


  • 0
    J

    Without considering the stack of recursive function calls, constructing the BST from bottom up is O(N) time and O(1) space.


  • 0
    L

    I doubt it. If you don't use an extra array which can access it's middle in constant time, how you build the tree recursively in O(n) time? Please briefly describe your tree building strategy.


  • 11

    The key is to create the nodes by the list's order in a bottom-up fashion. Read this article:
    Convert Sorted List to Balanced Binary Search Tree (BST) for an in-depth analysis and solution for this problem.


  • 0
    J

    You can construct from bottom up then no need to fetch the node to an array. Just like the other answer by 1337c0d3r said.


  • 3
    U

    Here is my python code with the same idea as others said.

    class Solution:
    # @param head, a list node
    # @return a tree node
    def sortedListToBST(self, head):
        if not head:
            return None
        N = 0
        cur = head
        while cur:
            N += 1
            cur = cur.next
        A = self.listToBST(head, N)
        return A[0]
    
    def listToBST(self, head, N):
        if N == 1:
            return [TreeNode(head.val), head.next]
        l = self.listToBST(head, N/2)
        root = TreeNode(l[1].val)
        root.left = l[0]
        if (N-1)/2:
            r = self.listToBST(l[1].next, (N-1)/2)
            root.right = r[0]
            return [root, r[1]]
        else:
            return [root, l[1].next]

  • 0
    P

    Thanks for sharing!


  • 0
    I

    The above code is so elegant but tricky. To understand the code, u can read this one http://www.geeksforgeeks.org/sorted-linked-list-to-balanced-bst/ which contain a better explanation.


  • 0
    C

    Both these solutions are not really O(1) in terms of space complexity. Considering the recursive call stack, they are O(logn).


  • 0
    N

    The solutions are not O(1) space, not only because of the recursion but because we're creating n nodes in memory for each new tree node


Log in to reply
 

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