Convert Sorted List to Binary Search Tree

Med

#0109Time: O(N log N)Space: O(log N)4 companies

Algorithms

Divide and Conquer

Data structures

Linked List Tree Binary Tree Binary Search Tree

Companies

Meta Uber Lyft Zenefits

Prompt

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

Example 1:

Input: head = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: One possible answer is [0,-3,9,-10,null,5], which represents the shown height balanced BST.

Example 2:

Input: head = []
Output: []

Constraints:

The number of nodes in head is in the range [0, 2 * 10⁴].
-10⁵ <= Node.val <= 10⁵

Approaches

3 approaches with complexity analysis and trade-offs.

This approach builds the BST directly from the linked list without converting it to another data structure. It recursively finds the middle node of the list to serve as the root and then splits the list into two halves to form the left and right subtrees.

Algorithm

Handle base cases: if the list segment is empty (head == tail), return null.
Use two pointers, slow and fast, to find the middle of the linked list segment [head, tail). slow moves one step, fast moves two. Initialize both to head.
Iterate while fast != tail and fast.next != tail.
Once the middle node (slow) is found, create a TreeNode with its value. This will be the root.
Recursively call the function for the left part, which is the segment [head, slow). The result is the left child of the root.
Recursively call the function for the right part, which is the segment [slow.next, tail). The result is the right child of the root.
Return the root.

Walkthrough

The core of this method is a recursive function that takes the head and tail of a linked list segment and returns the root of the constructed BST. The segment is represented as [head, tail).

To find the middle element, which will become the root of the tree, we use the classic two-pointer technique: a slow pointer that moves one step at a time and a fast pointer that moves two steps. When the fast pointer reaches the tail, the slow pointer will be at the middle of the segment.

The node pointed to by slow becomes the root of the current subtree.

The left subtree is recursively built from the list segment starting at the original head up to slow.
The right subtree is recursively built from the list segment starting at slow.next up to tail.
The base case for the recursion is when head and tail are the same, indicating an empty list segment.

1/**2 * Definition for singly-linked list.3 * public class ListNode {4 *     int val;5 *     ListNode next;6 *     ListNode() {}7 *     ListNode(int val) { this.val = val; }8 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }9 * }10 */11/**12 * Definition for a binary tree node.13 * public class TreeNode {14 *     int val;15 *     TreeNode left;16 *     TreeNode right;17 *     TreeNode() {}18 *     TreeNode(int val) { this.val = val; }19 *     TreeNode(int val, TreeNode left, TreeNode right) {20 *         this.val = val;21 *         this.left = left;22 *         this.right = right;23 *     }24 * }25 */26class Solution {27    public TreeNode sortedListToBST(ListNode head) {28        if (head == null) {29            return null;30        }31        return toBST(head, null);32    }33 34    private TreeNode toBST(ListNode head, ListNode tail) {35        if (head == tail) {36            return null;37        }38        39        ListNode slow = head;40        ListNode fast = head;41        42        // Find the middle node of the list segment [head, tail)43        while (fast != tail && fast.next != tail) {44            slow = slow.next;45            fast = fast.next.next;46        }47        48        // 'slow' is the middle node49        TreeNode root = new TreeNode(slow.val);50        root.left = toBST(head, slow);51        root.right = toBST(slow.next, tail);52        53        return root;54    }55}

Complexity

Time

O(N log N)

Space

O(log N)

Trade-offs

Pros

Space-efficient, using only O(log N) space for the recursion stack.
Operates on the linked list in-place without needing an auxiliary data structure to store all elements.

Cons

The time complexity of O(N log N) is suboptimal, as the list is repeatedly traversed to find the middle element for each subtree construction.

This approach first converts the sorted linked list into an array. Then, it constructs a height-balanced BST from this sorted array. This simplifies the problem to "Convert Sorted Array to Binary Search Tree", as random access is much easier with an array.

Algorithm

Traverse the linked list and store all node values into an ArrayList.
Define a recursive helper function buildTree(values, left, right) that constructs a BST from the subarray values[left...right].
In buildTree:
- If left > right, return null.
- Calculate the middle index mid = left + (right - left) / 2.
- Create a new TreeNode with values.get(mid) as the root.
- Set root.left to the result of buildTree(values, left, mid - 1).
- Set root.right to the result of buildTree(values, mid + 1, right).
- Return the root.
Initiate the process by calling buildTree with the full range of the array, (0, size - 1).

Walkthrough

The algorithm begins by iterating through the entire linked list and storing each node's value in a dynamic array, like an ArrayList in Java. This step takes O(N) time.

Once the array is populated, we have all the elements in sorted order. A recursive function is then used to build the BST. This function takes the start and end indices of the current segment of the array.

The middle element of the current array segment is chosen as the root of the subtree. This choice ensures the resulting tree is height-balanced.

The left child of the root is constructed by recursively calling the function on the left half of the array (elements before the middle element).
Similarly, the right child is constructed from the right half of the array.
The base case for the recursion is when the start index becomes greater than the end index, at which point null is returned.

1/**2 * Definition for singly-linked list.3 * public class ListNode {4 *     int val;5 *     ListNode next;6 *     ListNode() {}7 *     ListNode(int val) { this.val = val; }8 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }9 * }10 */11/**12 * Definition for a binary tree node.13 * public class TreeNode {14 *     int val;15 *     TreeNode left;16 *     TreeNode right;17 *     TreeNode() {}18 *     TreeNode(int val) { this.val = val; }19 *     TreeNode(int val, TreeNode left, TreeNode right) {20 *         this.val = val;21 *         this.left = left;22 *         this.right = right;23 *     }24 * }25 */26class Solution {27    public TreeNode sortedListToBST(ListNode head) {28        if (head == null) {29            return null;30        }31        32        // 1. Convert linked list to array33        List<Integer> values = new ArrayList<>();34        ListNode current = head;35        while (current != null) {36            values.add(current.val);37            current = current.next;38        }39        40        // 2. Build BST from the sorted array41        return buildTree(values, 0, values.size() - 1);42    }43    44    private TreeNode buildTree(List<Integer> values, int left, int right) {45        if (left > right) {46            return null;47        }48        49        // Find the middle element to be the root50        int mid = left + (right - left) / 2;51        TreeNode root = new TreeNode(values.get(mid));52        53        // Recursively build the left and right subtrees54        root.left = buildTree(values, left, mid - 1);55        root.right = buildTree(values, mid + 1, right);56        57        return root;58    }59}

Complexity

Time

O(N)

Space

O(N)

Trade-offs

Pros

Simple to understand and implement.
Leverages the efficiency of random access in arrays, which simplifies the logic for finding the middle element.
Time complexity is linear, which is efficient.

Cons

Requires extra space proportional to the number of nodes in the list (O(N)) to store the array. This can be significant for very large lists and may lead to memory issues.

This is the most optimal approach. It leverages the fact that the sorted linked list represents the inorder traversal of the target BST. The tree is constructed bottom-up by simulating an inorder traversal. We don't need to find the middle node repeatedly.

Algorithm

Count the number of nodes n in the linked list.
Maintain a pointer to the current head of the list (e.g., as a class member).
Define a recursive helper function buildTree(start, end) that builds a BST from the elements corresponding to indices start to end.
In buildTree:
- If start > end, return null.
- Calculate mid = start + (end - start) / 2.
- Recursively call buildTree(start, mid - 1) to build the left subtree.
- Create the root node using the value from the current head. Assign the returned left subtree to root.left.
- Advance the head pointer to the next node in the list.
- Recursively call buildTree(mid + 1, end) to build the right subtree. Assign the result to root.right.
- Return the root.
Start the process by calling buildTree(0, n - 1).

Walkthrough

The algorithm first determines the size of the linked list, say n. A single pointer to the head of the list is maintained (e.g., as a class field). This pointer will be advanced as we 'use up' nodes from the list to build the tree.

A recursive helper function is defined, which takes a range of indices (start, end) representing the portion of the list to be converted into a subtree.

The logic inside the recursive function mimics an inorder traversal:

Left: Recursively call the function for the left half of the indices, (start, mid - 1). This will construct the left subtree and consume the first mid - start nodes from the list.
Root: After the left subtree is built, the list pointer will be at the correct node for the current root. Create a TreeNode with this node's value and attach the constructed left subtree to it. Then, advance the list pointer.
Right: Recursively call the function for the right half of the indices, (mid + 1, end). This will construct the right subtree using the subsequent nodes. Attach the result as the right child of the root.

This way, we traverse the linked list only once and build the tree simultaneously.

1/**2 * Definition for singly-linked list.3 * public class ListNode {4 *     int val;5 *     ListNode next;6 *     ListNode() {}7 *     ListNode(int val) { this.val = val; }8 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }9 * }10 */11/**12 * Definition for a binary tree node.13 * public class TreeNode {14 *     int val;15 *     TreeNode left;16 *     TreeNode right;17 *     TreeNode() {}18 *     TreeNode(int val) { this.val = val; }19 *     TreeNode(int val, TreeNode left, TreeNode right) {20 *         this.val = val;21 *         this.left = left;22 *         this.right = right;23 *     }24 * }25 */26class Solution {27    private ListNode head;28 29    public TreeNode sortedListToBST(ListNode head) {30        if (head == null) {31            return null;32        }33        this.head = head;34        int size = getListSize(head);35        return buildTree(0, size - 1);36    }37 38    private int getListSize(ListNode head) {39        int size = 0;40        ListNode current = head;41        while (current != null) {42            size++;43            current = current.next;44        }45        return size;46    }47 48    private TreeNode buildTree(int start, int end) {49        if (start > end) {50            return null;51        }52 53        int mid = start + (end - start) / 2;54 55        // 1. Recursively build the left subtree56        TreeNode leftChild = buildTree(start, mid - 1);57 58        // 2. Create the root node59        // After the left subtree is built, `this.head` points to the root element60        TreeNode root = new TreeNode(this.head.val);61        root.left = leftChild;62 63        // 3. Move head pointer to the next element for the right subtree64        this.head = this.head.next;65 66        // 4. Recursively build the right subtree67        root.right = buildTree(mid + 1, end);68 69        return root;70    }71}

Complexity

Time

O(N)

Space

O(log N)

Trade-offs

Pros

Optimal time complexity of O(N).
Optimal space complexity of O(log N) for the recursion stack.
Traverses the linked list only once, making it very efficient.

Cons

The logic can be slightly less intuitive than the array-based approach.
Requires a class member or a mutable object to keep track of the list's head across recursive calls, which can be seen as a minor design drawback.

Solutions

Solution

1public class Convert_Sorted_List_to_Binary_Search_Tree { /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; next = null; } * } */ /** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public TreeNode sortedListToBST ( ListNode head ) { if ( head == null ) { return null ; } if ( head . next == null ) { return new TreeNode ( head . val ); } // find mid ListNode dummy = new ListNode ( 0 ); dummy . next = head ; ListNode slow = head , fast = head , prev = dummy ; while ( fast != null && fast . next != null ) { prev = slow ; slow = slow . next ; fast = fast . next . next ; } // prev is one before mid // ListNode 2ndPartHead = slow.next; // @note@note: illegal, cannot start with number ListNode newHead = slow . next ; prev . next = null ; // @note: cut TreeNode root = new TreeNode ( slow . val ); root . left = sortedListToBST ( head ); root . right = sortedListToBST ( newHead ); return root ; } } } ############ /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public TreeNode sortedListToBST ( ListNode head ) { List < Integer > nums = new ArrayList <>(); for (; head != null ; head = head . next ) { nums . add ( head . val ); } return buildBST ( nums , 0 , nums . size () - 1 ); } private TreeNode buildBST ( List < Integer > nums , int start , int end ) { if ( start > end ) { return null ; } int mid = ( start + end ) >> 1 ; TreeNode root = new TreeNode ( nums . get ( mid )); root . left = buildBST ( nums , start , mid - 1 ); root . right = buildBST ( nums , mid + 1 , end ); return root ; } }

1/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {ListNode} head * @return {TreeNode} */ var sortedListToBST =2  function (head) {3    const buildBST = (nums, start, end) => {4      if (start > end) {5        return null;6      }7      const mid = (start + end) >> 1;8      const root = new TreeNode(nums[mid]);9      root.left = buildBST(nums, start, mid - 1);10      root.right = buildBST(nums, mid + 1, end);11      return root;12    };13    const nums = new Array();14    for (; head != null; head = head.next) {15      nums.push(head.val);16    }17    return buildBST(nums, 0, nums.length - 1);18  };

1# Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution : def sortedListToBST ( self , head : Optional [ ListNode ]) -> Optional [ TreeNode ]: if not head : return None if not head . next : return TreeNode ( head . val ) # find mid dummy = ListNode ( 0 ) dummy . next = head slow , fast , prev = head , head , dummy while fast and fast . next : prev = slow slow = slow . next fast = fast . next . next # prev is one before mid new_head = slow . next prev . next = None # cut root = TreeNode ( slow . val ) root . left = self . sortedListToBST ( head ) root . right = self . sortedListToBST ( new_head ) return root ################# class Solution : # convert to array[], extra space => but resue method in 108 def sortedListToBST ( self , head : ListNode ) -> TreeNode : def buildBST ( nums , start , end ): if start > end : return None mid = ( start + end ) >> 1 return TreeNode ( nums [ mid ], buildBST ( nums , start , mid - 1 ), buildBST ( nums , mid + 1 , end ) ) nums = [] while head : nums . append ( head . val ) head = head . next return buildBST ( nums , 0 , len ( nums ) - 1 )

1// OJ: https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/ // Time: O(NlogN) // Space: O(logN) class Solution { int getLength ( ListNode * head ) { int ans = 0 ; for (; head ; head = head -> next , ++ ans ); return ans ; } TreeNode * dfs ( ListNode * head , int len ) { if ( len == 0 ) return NULL ; if ( len == 1 ) return new TreeNode ( head -> val ); auto p = head ; for ( int i = 0 ; i < len / 2 ; ++ i ) p = p -> next ; auto root = new TreeNode ( p -> val ); root -> left = dfs ( head , len / 2 ); root -> right = dfs ( p -> next , ( len - 1 ) / 2 ); return root ; } public: TreeNode * sortedListToBST ( ListNode * head ) { int len = getLength ( head ); return dfs ( head , len ); } };

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1public class Convert_Sorted_List_to_Binary_Search_Tree { /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; next = null; } * } */ /** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public TreeNode sortedListToBST ( ListNode head ) { if ( head == null ) { return null ; } if ( head . next == null ) { return new TreeNode ( head . val ); } // find mid ListNode dummy = new ListNode ( 0 ); dummy . next = head ; ListNode slow = head , fast = head , prev = dummy ; while ( fast != null && fast . next != null ) { prev = slow ; slow = slow . next ; fast = fast . next . next ; } // prev is one before mid // ListNode 2ndPartHead = slow.next; // @note@note: illegal, cannot start with number ListNode newHead = slow . next ; prev . next = null ; // @note: cut TreeNode root = new TreeNode ( slow . val ); root . left = sortedListToBST ( head ); root . right = sortedListToBST ( newHead ); return root ; } } } ############ /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public TreeNode sortedListToBST ( ListNode head ) { List < Integer > nums = new ArrayList <>(); for (; head != null ; head = head . next ) { nums . add ( head . val ); } return buildBST ( nums , 0 , nums . size () - 1 ); } private TreeNode buildBST ( List < Integer > nums , int start , int end ) { if ( start > end ) { return null ; } int mid = ( start + end ) >> 1 ; TreeNode root = new TreeNode ( nums . get ( mid )); root . left = buildBST ( nums , start , mid - 1 ); root . right = buildBST ( nums , mid + 1 , end ); return root ; } }

1/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {ListNode} head * @return {TreeNode} */ var sortedListToBST =2  function (head) {3    const buildBST = (nums, start, end) => {4      if (start > end) {5        return null;6      }7      const mid = (start + end) >> 1;8      const root = new TreeNode(nums[mid]);9      root.left = buildBST(nums, start, mid - 1);10      root.right = buildBST(nums, mid + 1, end);11      return root;12    };13    const nums = new Array();14    for (; head != null; head = head.next) {15      nums.push(head.val);16    }17    return buildBST(nums, 0, nums.length - 1);18  };

1# Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution : def sortedListToBST ( self , head : Optional [ ListNode ]) -> Optional [ TreeNode ]: if not head : return None if not head . next : return TreeNode ( head . val ) # find mid dummy = ListNode ( 0 ) dummy . next = head slow , fast , prev = head , head , dummy while fast and fast . next : prev = slow slow = slow . next fast = fast . next . next # prev is one before mid new_head = slow . next prev . next = None # cut root = TreeNode ( slow . val ) root . left = self . sortedListToBST ( head ) root . right = self . sortedListToBST ( new_head ) return root ################# class Solution : # convert to array[], extra space => but resue method in 108 def sortedListToBST ( self , head : ListNode ) -> TreeNode : def buildBST ( nums , start , end ): if start > end : return None mid = ( start + end ) >> 1 return TreeNode ( nums [ mid ], buildBST ( nums , start , mid - 1 ), buildBST ( nums , mid + 1 , end ) ) nums = [] while head : nums . append ( head . val ) head = head . next return buildBST ( nums , 0 , len ( nums ) - 1 )

1// OJ: https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/ // Time: O(NlogN) // Space: O(logN) class Solution { int getLength ( ListNode * head ) { int ans = 0 ; for (; head ; head = head -> next , ++ ans ); return ans ; } TreeNode * dfs ( ListNode * head , int len ) { if ( len == 0 ) return NULL ; if ( len == 1 ) return new TreeNode ( head -> val ); auto p = head ; for ( int i = 0 ; i < len / 2 ; ++ i ) p = p -> next ; auto root = new TreeNode ( p -> val ); root -> left = dfs ( head , len / 2 ); root -> right = dfs ( p -> next , ( len - 1 ) / 2 ); return root ; } public: TreeNode * sortedListToBST ( ListNode * head ) { int len = getLength ( head ); return dfs ( head , len ); } };

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.