Leetcode 109. Convert Sorted List to Binary Search Tree

Question

Given an ascending linked list and generate a balanced binary search tree.

Solution

The key of the algorithm is to take the mid point as the root node. However, linked list here does not support random access.

One of the most commonly used method to find mid point in linked list is to use fast and slow pointers.

The fast pointer and the slow pointer traverse from the head at the same time. The fast pointer takes two steps at a time, and the slow pointer takes one step at a time. When the fast pointer reaches the end of the list, the slow pointer points to the mid position.

public static TreeNode sortedListToBST(ListNode head) {
    return findMiddle(head, null);
}

// need to find the middle node in the linked list
private static TreeNode findMiddle(ListNode start, ListNode end) {
    if (start == end) {
        return null;
    }

    // slow and fast pointer to find middle node
    ListNode slow = start;
    ListNode fast = start;

    while (fast != end && fast.next != end) {
        slow = slow.next;
        fast = fast.next.next;
    }

    // slow is the middle point
    TreeNode root = new TreeNode(slow.val);
    root.left = findMiddle(start, slow);
    root.right = findMiddle(slow.next, end);

    return root;
}

Time complexity: according to the recursive formula, T(n) = 2 * T(n / 2) + n = O(nlog(n)).

Space complexity: O(log(n)).

Question

Similar Question

Solution