109. Convert Sorted List to Binary Search Tree

Description

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 differ by more than 1.

Constraints

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

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

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

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: []

Example 3

Input: head = [0]

Output: [0]

Example 4

Input: head = [1, 3]

Output: [3, 1]

Solutions

ListNode

// 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;
	}
}

TreeNode

// 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;
    }
}

Solution 1

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if(head == null) return null;
        
        ListNode mid = findMiddleElement(head);
        
        TreeNode node = new TreeNode(mid.val);
        
        if(head == mid) return node;
        
        node.left = sortedListToBST(head);
        
        node.right = sortedListToBST(mid.next);
        
        return node;
    }
    
    private ListNode findMiddleElement(ListNode head) {
        ListNode prevPtr = null;
        ListNode slowPtr = head;
        ListNode fastPtr = head;
        
        while(fastPtr != null && fastPtr.next != null) {
            prevPtr = slowPtr;
            slowPtr = slowPtr.next;
            fastPtr = fastPtr.next.next;
        }
        
        // Handling the case when slowPtr was equal to head.
        if(prevPtr != null) prevPtr.next = null;
        
        return slowPtr;
    }
}

Solution 2

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {

  private List<Integer> values;

  public Solution() {
    this.values = new ArrayList<Integer>();
  }

  private void mapListToValues(ListNode head) {
    while (head != null) {
      this.values.add(head.val);
      head = head.next;
    }
  }

  private TreeNode convertListToBST(int left, int right) {
    // Invalid case
    if (left > right) {
      return null;
    }

    // Middle element forms the root.
    int mid = (left + right) / 2;
    TreeNode node = new TreeNode(this.values.get(mid));

    // Base case for when there is only one element left in the array
    if (left == right) {
      return node;
    }

    // Recursively form BST on the two halves
    node.left = convertListToBST(left, mid - 1);
    node.right = convertListToBST(mid + 1, right);
    return node;
  }

  public TreeNode sortedListToBST(ListNode head) {

    // Form an array out of the given linked list and then
    // use the array to form the BST.
    this.mapListToValues(head);

    // Convert the array to
    return convertListToBST(0, this.values.size() - 1);
  }
}

Solution 3

/**
 * Time complexity : 
 * Space complexity : 
 */
 
 class Solution {
    private ListNode currNode;
    
    public TreeNode sortedListToBST(ListNode head) {
        if(head == null) {
            return null;
        }
        int listLen = length(head);
        currNode = head;
        return sortedListToBST(0, listLen-1);
    }
    
    private TreeNode sortedListToBST(int start, int end) {
        if(start > end) {
            return null;
        }
        int mid = start + (end - start)/2;
        TreeNode left = sortedListToBST(start, mid-1);
        
        TreeNode root = new TreeNode(currNode.val);
        currNode = currNode.next;
        
        TreeNode right = sortedListToBST(mid+1, end);
        
        root.left = left;
        root.right = right;
        
        return root;
    }
    
    private int length(ListNode node) {
        int l = 0;
        while(node != null) {
            l++;
            node = node.next;
        }
        return l;
    }
}

Follow up