Problem

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

A height balanced BST: a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Examples

Example 1:

Input: nums = [1, 2, 3, 4, 5, 6]
Output: [3,2,5,1,null,4,6]
Explanation: [4,2,5,1,3,null,6] is also accepted.

These are the two height-balanced binary tree, with height = 3:

    3
   / \
  2   5
 /   / \
1   4   6

OR

    4
   / \
  2   5
 / \   \
1   3   6

Note, that we may also get skewed binary search tree, but we don’t want that, height = 6 is not minimum

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

Solution

If given an array, the problem is straightforward. We have addressed it in Convert Sorted Array to height-balanced Binary Search Tree.

However, the complexity increases when working with a singly linked list as opposed to an array. Without O(1) random access, we must construct nodes from the bottom up, assigning them to their parent nodes. This bottom-up approach allows sequential access to the list while creating nodes.

Method 1 - Recursion and calculating length of list

One challenge is that we cannot directly access the middle element (root) in a list without traversal. This can be addressed using recursion, passing the start and end indices to define the list segment for the left subtree. The next element to process will then be the middle element.

We can get the length of the list using Find the length of the linked list, and then calculate mid = (0 + len) / 2.

Here are the steps:

  • Identify the middle node as mid.
  • Recursively build the left subtree from start to mid-1.
  • Assign the middle node as the root and attach the left subtree.
  • Recursively build the right subtree from mid+1 to end.
  • Attach the right subtree to the root.

Here is how the buildTree() function works:

  • Recursively constructs the tree.
  • Uses in-order traversal to build the tree from the linked list. The current pointer advances through the list as nodes are assigned.
  • Splits the list into left and right parts and recursively constructs the left and right subtrees.

Code

Java
public class Solution {

	private ListNode current;

	public TreeNode sortedListToBST(ListNode head) {
		if (head == null) {
			return null;
		}

		int length = getLength(head);
		current = head;
		return buildTree(0, length - 1);
	}

	private int getLength(ListNode head) {
		int length = 0;
		ListNode temp = head;

		while (temp != null) {
			length++;
			temp = temp.next;
		}

		return length;
	}

	private TreeNode buildTree(int start, int end) {
		if (start > end) {
			return null;
		}

		int mid = (start + end) / 2;

		TreeNode leftChild = buildTree(start, mid - 1);

		TreeNode node = new TreeNode(current.val);
		current = current.next;

		TreeNode rightChild = buildTree(mid + 1, end);

		node.left = leftChild;
		node.right = rightChild;

		return node;
	}
}

Complexity

  • ⏰ Time complexity: O(n) where is the linked list length. It takes O(n) time to get the length of list, and the O(n) for buildTree function
  • 🧺 Space complexity: O(h), assuming recursion stack

Method 2 - Recursion but using slow and fast pointer

To achieve the conversion, we can use a bottom-up approach. The idea is to recursively create the tree from the middle of the list. We will use a two-pointer technique to find the middle element of the list, which will become the root of the BST.

Steps

  1. Use the slow and fast pointer technique to find the middle of the linked list.
  2. The middle element will be the root of the BST.
  3. Recursively do the same for the left half and the right half of the linked list to form the left and right subtrees.

Code

Java
public class Solution {

	public TreeNode sortedListToBST(ListNode head) {
		if (head == null) {
			return null;
		}

		return buildTree(head, null);
	}

	private TreeNode buildTree(ListNode head, ListNode end) {
		if (head == end) {
			return null;
		}

		ListNode mid = findMiddle(head, end);
		TreeNode node = new TreeNode(mid.val);

		node.left = buildTree(head, mid);
		node.right = buildTree(mid.next, end);

		return node;
	}

	private ListNode findMiddle(ListNode head, ListNode end) {
		ListNode slow = head;
		ListNode fast = head;

		while (fast != end && fast.next != end) {
			slow = slow.next;
			fast = fast.next.next;
		}

		return slow;
	}
}

Complexity

  • ⏰ Time complexity: O(n) where is the linked list length. buildTree() function takes O(n) time
  • 🧺 Space complexity: O(h), assuming recursion stack