Jobs

Interviews

Discussions

Convert Sorted List to Binary Search Tree

Medium

Convert Sorted List to Binary Search Tree

Medium

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the linked list be empty or contain null values?
What is the expected behavior if the linked list has an even number of nodes; should the root be the 'middle' or the node immediately to its left?
Can the linked list contain duplicate values, and if so, how should they be handled in the resulting BST?
What is the acceptable range of values for the nodes in the linked list (e.g., can they be negative, or are there any integer overflow considerations)?
Are we aiming for a balanced BST, or is any valid BST acceptable?

Brute Force Solution

Approach

We want to build a perfectly balanced tree from a sorted list. The brute force method tries every conceivable tree shape, checking each one to see if it meets our conditions, like being balanced and keeping the sorted order from the list.

Here's how the algorithm would work step-by-step:

Consider every possible element from the list as the root of the tree.
For each choice of root, split the remaining list into two parts: elements that could be in the left subtree and elements that could be in the right subtree.
For each potential left subtree, recursively try all possible tree structures you can build with those elements. Do the same for the potential right subtree.
Combine each possible left subtree with the root and each possible right subtree to form a complete tree.
Check if the constructed tree is a valid binary search tree (meaning the sorted order is maintained).
Also verify that the tree is height-balanced (meaning the heights of the left and right subtrees of every node differ by at most 1).
Keep track of all the trees that satisfy both conditions (sorted order and height balance).
If multiple valid trees are found, pick one, perhaps arbitrarily, or based on some other criteria you define. If no valid trees are found, the input was invalid.

Code Implementation

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def convert_sorted_list_to_bst(sorted_list):
    def is_binary_search_tree(root, min_value=float('-inf'), max_value=float('inf')):
        if not root:
            return True
        if root.value <= min_value or root.value >= max_value:
            return False
        return is_binary_search_tree(root.left, min_value, root.value) and \
               is_binary_search_tree(root.right, root.value, max_value)

    def is_height_balanced(root):
        def get_height(node):
            if not node:
                return 0
            return 1 + max(get_height(node.left), get_height(node.right))

        if not root:
            return True

        left_height = get_height(root.left)
        right_height = get_height(root.right)

        if abs(left_height - right_height) > 1:
            return False

        return is_height_balanced(root.left) and is_height_balanced(root.right)

    def generate_trees(sub_list):
        if not sub_list:
            return [None]

        trees = []
        for index in range(len(sub_list)):
            root_value = sub_list[index]
            # Consider current element as root

            left_sub_list = sub_list[:index]
            right_sub_list = sub_list[index+1:]

            left_subtrees = generate_trees(left_sub_list)
            right_subtrees = generate_trees(right_sub_list)

            # Construct all possible trees with this root
            for left_subtree in left_subtrees:
                for right_subtree in right_subtrees:
                    root = TreeNode(root_value)
                    root.left = left_subtree
                    root.right = right_subtree
                    trees.append(root)
        return trees

    all_possible_trees = generate_trees(sorted_list)

    valid_trees = []
    for tree in all_possible_trees:
        if is_binary_search_tree(tree) and is_height_balanced(tree):
            # Check BST and height balance condition
            valid_trees.append(tree)

    if valid_trees:
        return valid_trees[0]
        # Return a valid tree
    else:
        return None
        # No valid tree found

Big(O) Analysis

Time Complexity

O(4^n / n^(3/2)) – The described brute force approach explores all possible binary tree structures that can be formed from the sorted list. The number of possible binary trees that can be formed from n nodes is given by the Catalan number, which is approximately 4^n / (n^(3/2) * sqrt(pi)). For each of these trees, we need to validate if it is a binary search tree and height balanced which takes O(n) time. Thus, the overall time complexity is O(n * 4^n / n^(3/2)), which simplifies to O(4^n / n^(3/2)).

Space Complexity

O(N^2) – The brute force method explores every possible tree structure. The recursive calls, where each call splits the list into left and right subtrees, can create a call stack of depth up to N in the worst case (skewed tree), where N is the number of elements in the list. Also, the creation of sublists during each recursive call contributes to space complexity. The intermediate storage of multiple potential subtrees grows as different combinations are tested. In the worst case, storing all potential subtrees during the recursion could approximate N for the depth, with N for the sublists themselves for a total space complexity of O(N^2).

Optimal Solution

Approach

The best way to solve this problem is to build the tree from the middle out. This ensures we create a balanced tree directly, which is key for optimal performance. By picking the middle element as the root, we naturally divide the problem into smaller, similar subproblems.

Here's how the algorithm would work step-by-step:

Find the middle element of the sorted list. This element will be the root of our binary search tree.
Divide the list into two halves: the elements to the left of the middle, and the elements to the right.
Recursively build the left subtree using the left half of the list. The middle element of the left half becomes the root of the left subtree.
Recursively build the right subtree using the right half of the list. The middle element of the right half becomes the root of the right subtree.
Connect the left and right subtrees to the root we chose in the first step.
Repeat this process until all elements from the sorted list are incorporated into the binary search tree. Each time we pick the middle, we make sure the tree stays balanced.

Code Implementation

class TreeNode:
    def __init__(self, value=0, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

class ListNode:
    def __init__(self, value=0, next_node=None):
        self.value = value
        self.next_node = next_node

def sorted_list_to_bst(head):
    def find_middle(head_node):
        slow_pointer = head_node
        fast_pointer = head_node
        previous_node = None

        while fast_pointer and fast_pointer.next_node:
            previous_node = slow_pointer
            slow_pointer = slow_pointer.next_node
            fast_pointer = fast_pointer.next_node.next_node

        return previous_node, slow_pointer

    def build_bst(head_node):
        if not head_node:
            return None

        previous_node, middle_node = find_middle(head_node)

        # If list has more than one element,
        # break the list into two halves
        if previous_node:
            previous_node.next_node = None

        # The middle element is the root
        root = TreeNode(middle_node.value)

        # If list only had one element,
        # make it the root and return.
        if head_node == middle_node:
            return root

        # Recursively build the left subtree
        root.left = build_bst(head_node)

        # Recursively build the right subtree
        root.right = build_bst(middle_node.next_node)

        return root

    return build_bst(head)

Big(O) Analysis

Time Complexity

O(n) – The algorithm processes each node in the linked list exactly once. Finding the middle element of the list in each recursive call takes O(n) time if we were to traverse the list. However, since we are using the sorted nature of the list and implicitly dividing the list at the middle in each recursive call, we are only visiting each node once. Consequently, building the tree takes O(n) time in total, as each node becomes part of the tree in a divide and conquer fashion. Each recursive call effectively splits the list into smaller halves, with a maximum of n calls.

Space Complexity

O(log N) – The algorithm uses recursion to build the binary search tree. The maximum depth of the recursion is proportional to the height of the tree, which, since the tree is balanced, is log N, where N is the number of nodes (elements in the sorted list). Each recursive call adds a new frame to the call stack, so the maximum space used by the call stack is O(log N). No other significant auxiliary space is used.

Edge Cases

Case	How to Handle
Null input list	Return null, indicating an empty tree for null input.
Empty input list	Return null, representing an empty tree.
List with a single node	Create a single node BST with the value of that node from the list.
List with two nodes	Create a BST with the first node as the root, and the second as the right child.
List with many nodes (scalability)	The algorithm should use recursion, which may lead to stack overflow; an iterative approach might be preferable for extremely large lists.
List with duplicate values	The algorithm should correctly construct a BST regardless of duplicate values in the list.
List with negative and positive values	The algorithm should correctly handle both negative and positive values without any special modifications.
Skewed list (e.g., almost sorted, or almost reverse sorted)	The resulting BST might be highly unbalanced if the list is skewed, potentially leading to O(n) search time in worst-case scenarios, and balancing algorithms might be needed.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the linked list be empty or contain null values?
What is the expected behavior if the linked list has an even number of nodes; should the root be the 'middle' or the node immediately to its left?
Can the linked list contain duplicate values, and if so, how should they be handled in the resulting BST?
What is the acceptable range of values for the nodes in the linked list (e.g., can they be negative, or are there any integer overflow considerations)?
Are we aiming for a balanced BST, or is any valid BST acceptable?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Consider every possible element from the list as the root of the tree.
For each choice of root, split the remaining list into two parts: elements that could be in the left subtree and elements that could be in the right subtree.
For each potential left subtree, recursively try all possible tree structures you can build with those elements. Do the same for the potential right subtree.
Combine each possible left subtree with the root and each possible right subtree to form a complete tree.
Check if the constructed tree is a valid binary search tree (meaning the sorted order is maintained).
Also verify that the tree is height-balanced (meaning the heights of the left and right subtrees of every node differ by at most 1).
Keep track of all the trees that satisfy both conditions (sorted order and height balance).
If multiple valid trees are found, pick one, perhaps arbitrarily, or based on some other criteria you define. If no valid trees are found, the input was invalid.

Code Implementation

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def convert_sorted_list_to_bst(sorted_list):
    def is_binary_search_tree(root, min_value=float('-inf'), max_value=float('inf')):
        if not root:
            return True
        if root.value <= min_value or root.value >= max_value:
            return False
        return is_binary_search_tree(root.left, min_value, root.value) and \
               is_binary_search_tree(root.right, root.value, max_value)

    def is_height_balanced(root):
        def get_height(node):
            if not node:
                return 0
            return 1 + max(get_height(node.left), get_height(node.right))

        if not root:
            return True

        left_height = get_height(root.left)
        right_height = get_height(root.right)

        if abs(left_height - right_height) > 1:
            return False

        return is_height_balanced(root.left) and is_height_balanced(root.right)

    def generate_trees(sub_list):
        if not sub_list:
            return [None]

        trees = []
        for index in range(len(sub_list)):
            root_value = sub_list[index]
            # Consider current element as root

            left_sub_list = sub_list[:index]
            right_sub_list = sub_list[index+1:]

            left_subtrees = generate_trees(left_sub_list)
            right_subtrees = generate_trees(right_sub_list)

            # Construct all possible trees with this root
            for left_subtree in left_subtrees:
                for right_subtree in right_subtrees:
                    root = TreeNode(root_value)
                    root.left = left_subtree
                    root.right = right_subtree
                    trees.append(root)
        return trees

    all_possible_trees = generate_trees(sorted_list)

    valid_trees = []
    for tree in all_possible_trees:
        if is_binary_search_tree(tree) and is_height_balanced(tree):
            # Check BST and height balance condition
            valid_trees.append(tree)

    if valid_trees:
        return valid_trees[0]
        # Return a valid tree
    else:
        return None
        # No valid tree found

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Find the middle element of the sorted list. This element will be the root of our binary search tree.
Divide the list into two halves: the elements to the left of the middle, and the elements to the right.
Recursively build the left subtree using the left half of the list. The middle element of the left half becomes the root of the left subtree.
Recursively build the right subtree using the right half of the list. The middle element of the right half becomes the root of the right subtree.
Connect the left and right subtrees to the root we chose in the first step.
Repeat this process until all elements from the sorted list are incorporated into the binary search tree. Each time we pick the middle, we make sure the tree stays balanced.

Code Implementation

class TreeNode:
    def __init__(self, value=0, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

class ListNode:
    def __init__(self, value=0, next_node=None):
        self.value = value
        self.next_node = next_node

def sorted_list_to_bst(head):
    def find_middle(head_node):
        slow_pointer = head_node
        fast_pointer = head_node
        previous_node = None

        while fast_pointer and fast_pointer.next_node:
            previous_node = slow_pointer
            slow_pointer = slow_pointer.next_node
            fast_pointer = fast_pointer.next_node.next_node

        return previous_node, slow_pointer

    def build_bst(head_node):
        if not head_node:
            return None

        previous_node, middle_node = find_middle(head_node)

        # If list has more than one element,
        # break the list into two halves
        if previous_node:
            previous_node.next_node = None

        # The middle element is the root
        root = TreeNode(middle_node.value)

        # If list only had one element,
        # make it the root and return.
        if head_node == middle_node:
            return root

        # Recursively build the left subtree
        root.left = build_bst(head_node)

        # Recursively build the right subtree
        root.right = build_bst(middle_node.next_node)

        return root

    return build_bst(head)

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null input list	Return null, indicating an empty tree for null input.
Empty input list	Return null, representing an empty tree.
List with a single node	Create a single node BST with the value of that node from the list.
List with two nodes	Create a BST with the first node as the root, and the second as the right child.
List with many nodes (scalability)	The algorithm should use recursion, which may lead to stack overflow; an iterative approach might be preferable for extremely large lists.
List with duplicate values	The algorithm should correctly construct a BST regardless of duplicate values in the list.
List with negative and positive values	The algorithm should correctly handle both negative and positive values without any special modifications.
Skewed list (e.g., almost sorted, or almost reverse sorted)	The resulting BST might be highly unbalanced if the list is skewed, potentially leading to O(n) search time in worst-case scenarios, and balancing algorithms might be needed.