0109. Convert Sorted List to Binary Search Tree

Medium | Binary Search Tree + Inorder Traversal | 108 ms (99.14%), 25.4 MB (58.06%)

❓ Problem Statement

Source: LeetCode - Convert Sorted List to Binary Search Tree GitHub: Solution / Performance

Given the head of a singly linked list where elements are sorted in ascending order, convert it to a height-balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differs by more than 1.

✍🏻 Constraints & Example

Constraints:

• The number of nodes in head is in the range [0, 2 * 10^4].

• -10^5 <= Node.val <= 10^5

💡 Ideas

Inorder traversal of BST is an array sorted in ascending order.

Based on the above understanding, we could use two indexes "Start and End" to simulate inorder traversal recursively by the DFS method.

Besides, whenever we meet a left-child node, we record the current head node's value and then move the head node to the next node before finding the right-child node so that each node's value is assigned in an inorder traversal manner.

# pseudo code
mid = (start + end) // 2

leftNode  = dfs(start, mid - 1)
val  = head.val
head = head.next
rightNode = dfs(mid + 1, end)

node = TreNode(val, left, right)
return node

Consider above diagram for example [-10, -1, 5, 64, 77, 100]

🤖 Python3

class Solution:
    def sortedListToBST(self, head: ListNode) -> TreeNode:
        # (base case)
        if not head: return None
        if not head.next: return TreeNode(head.val)
        
        # ==================================================
        #  Linked List + Tree + In-order Recursion         =
        # ==================================================
        # time  : O(n)
        # space : O(log(n)) due to height-balanced BST
        
        cur, size = head, 0
        while cur:
            size += 1
            cur = cur.next
        
        self.head = head
        return self.inOrder(0, size - 1)
        
    def inOrder(self, start: int, end: int) -> TreeNode:
        if start > end: return None
        
        mid = (start + end) // 2
        
        left = self.inOrder(start, mid - 1)
        val = self.head.val
        self.head = self.head.next
        right = self.inOrder(mid + 1, end)
        
        node = TreeNode(val, left, right)
        
        return node

🤖 Java

class Solution {
    /**
     * @time  : O(nlog(n))
     * @space : O(log(n)) due to height-balanced BST
     */
     
    public ListNode findMid(ListNode head) {
        ListNode prevP = null, slowP = head, fastP = head;
        
        while(fastP != null && fastP.next != null) {
            prevP = slowP;
            slowP = slowP.next;
            fastP = fastP.next.next;
        }
        
        if(prevP != null) prevP.next = null;
        return slowP;
    }
    
    public TreeNode sortedListToBST(ListNode head) {
        /* base case */
        if(head == null) return null;
        if(head.next == null) return new TreeNode(head.val);
        
        ListNode mid = findMid(head);
        
        TreeNode node = new TreeNode(mid.val);
        node.left     = sortedListToBST(head);
        node.right    = sortedListToBST(mid.next);
        
        return node;
    }
}