109. Convert Sorted List to Binary Search Tree

// LeetCode URL: https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/

//   Definition for singly-linked list.
// class ListNode {
//     int val;
//     ListNode next;

//     ListNode(int x) {
//         val = x;
//     }
// }

// Definition for a binary tree node.
// class TreeNode {
//     int val;
//     TreeNode left;
//     TreeNode right;

//     TreeNode(int x) {
//         val = x;
//     }
// }

/**
 * Recursion and finding the mid point of the list
 *
 * Time Complexity: O(N^2). T(n) = 2 * T(n/2) + O(n/2)
 *
 * Space Complexity: O(H) = O(log N)
 *
 * N = Number of nodes on the input list. H = Height of the resultant tree.
 * Since the tree is height balanced, height will be log N.
 */
class Solution1 {
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            return new TreeNode(head.val);
        }

        return sortedListToBSTHelper(head, null);
    }

    private TreeNode sortedListToBSTHelper(ListNode left, ListNode right) {
        if (left == right) {
            return null;
        }

        ListNode fast = left;
        ListNode slow = left;
        while (fast != right && fast.next != right) {
            fast = fast.next.next;
            slow = slow.next;
        }

        TreeNode subTreeHead = new TreeNode(slow.val);
        subTreeHead.left = sortedListToBSTHelper(left, slow);
        subTreeHead.right = sortedListToBSTHelper(slow.next, right);

        return subTreeHead;
    }
}

/**
 * Inorder Simulation
 *
 * Refer:
 * https://leetcode.com/articles/convert-sorted-list-to-binary-search-tree/#approach-3-inorder-simulation
 *
 * Time Complexity: O(N)
 *
 * Space Complexity: O(H) = O(log N)
 *
 * N = Number of nodes on the input list. H = Height of the resultant tree.
 * Since the tree is height balanced, height will be log N.
 */
class Solution2 {
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            return new TreeNode(head.val);
        }

        int listSize = getListSize(head);

        ListNode[] listNextNode = new ListNode[] { head };

        return convertListToBST(listNextNode, 0, listSize - 1);
    }

    private int getListSize(ListNode head) {
        ListNode cur = head;
        int count = 0;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

    private TreeNode convertListToBST(ListNode[] listNextNode, int left, int right) {
        // Invalid Case
        if (left > right) {
            return null;
        }

        // if Both left and right are equal, then leaf node is created.
        if (left == right) {
            return getNextTreeNode(listNextNode);
        }

        int mid = left + (right - left) / 2;

        // First step of simulated inorder traversal. Recursively form the left half
        TreeNode leftSubTree = convertListToBST(listNextNode, left, mid - 1);

        // Once left half is traversed, process the current node
        TreeNode node = getNextTreeNode(listNextNode);

        node.left = leftSubTree;
        // Recurse on the right hand side and form BST out of them
        node.right = convertListToBST(listNextNode, mid + 1, right);

        return node;
    }

    private TreeNode getNextTreeNode(ListNode[] listNextNode) {
        TreeNode node = new TreeNode(listNextNode[0].val);
        listNextNode[0] = listNextNode[0].next;
        return node;
    }
}