LeetCode: Convert Sorted List to Binary Search Tree

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

---

We can construct the tree recursively. First step is to find the size of the linked list and then left part of the list will be the left subtree and right part of the list will be the right subtree.

C++ Code:

/* 
 * func: sorted_list_to_BST_helper
 * goal: recursive function to construct BST
 * @param head: head node of the linked list
 * @param start: start index
 * @param end: end index
 * return: root node of the tree
 */
TreeNode *sorted_list_to_BST_helper(ListNode *&head, int start, int end){
    if(start > end)
        return nullptr;
    
    int mid = start + (end - start) / 2;
    TreeNode *left = sorted_list_to_BST_helper(head, start, mid-1);
    TreeNode *root = new TreeNode(head->val);
    root->left = left;
    head = head->next;
    root->right = sorted_list_to_BST_helper(head, mid+1, end);
    return root;
}

/*
 * func: sorted_list_to_BST
 * goal: convert a sorted linked list to BST
 * @param head: head node of the linked list
 * return: root node of the tree
 */
TreeNode *sorted_list_to_BST(ListNode *head){
    ListNode *it = head;
    int length = 0;
    while(it){
        ++length;
        it = it->next;
    }
    
    return sorted_list_to_BST_helper(head, 0, length-1);
}

Python Code:

# func: convert sorted list to BST
# @param head: head node of the list
# @return: root node of the tree
def sorted_list_to_BST(head):
    def sorted_list_to_BST_helper(head, start, end):
        if start > end:
            return head, None
        mid = start + (end - start) / 2
        head, left_child = sorted_list_to_BST_helper(head, start, mid-1)
        root = TreeNode(head.val)
        head = head.next
        root.left = left_child
        head, root.right = sorted_list_to_BST_helper(head, mid+1, end)
        return head, root
    #Count the total number
    it = head
    count = 0
    while it:
        count += 1
        it = it.next


    head, root = sorted_list_to_BST_helper(head, 0, count-1)
    return root