# 109. Convert Sorted List to Binary Search Tree

## Solution1: use 108, convert to list then do the same.

T: O(2n)

```java
class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        List<Integer> list = new ArrayList<>();
        ListNode temp = head;
        while (temp != null) {
            list.add(temp.val);
            temp = temp.next;
        }
        return dfs(list, 0, list.size()-1);
    }
    private TreeNode dfs(List<Integer> list, int left, int right) {
        if (left > right) {
            return null;
        }
        int mid = (left + right)/2;
        TreeNode root = new TreeNode(list.get(mid));
        root.left = dfs(list, left, mid-1); 
        root.right = dfs(list, mid + 1, right); 
        return root;
    }
}

```

## solution 2: use slow fast pointer to find mid

and dfs(head, null) to build BS tree

slower than solution1, because needs to find mid every time...

```java
/**
 * 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) {
        return dfs(head, null);
    }
    private TreeNode dfs(ListNode begin, ListNode end) {
        if (begin == end) {
            return null;
        }
        ListNode mid = findMid(begin, end); // (5, 9), mid = 5
        TreeNode root = new TreeNode(mid.val); // 5
        root.left = dfs(begin, mid);  // 5,5 -> means it finished
        root.right = dfs(mid.next, end);
        return root;
    }
    private ListNode findMid(ListNode begin, ListNode end) { // exclude end
        ListNode fast = begin;
        ListNode slow = begin;
        while (fast != end && fast.next != end) {
            fast = fast.next.next; // 9
            slow = slow.next; // 0
        }
        return slow;
    }
}

/***

-10 -3 1    0    5 6 9

      0
    /.  \ 
    -3   6
    /\.  /\
  -10 1 5 9

  so it actually asks find max node, then do left part , right part DFS
 */
```

## Solution3: directly uses inorder&#x20;

T: O(n)

```java
class Solution {
    private ListNode cur;
    public TreeNode sortedListToBST(ListNode head) {
        int len = 0;
        ListNode temp = head;
        while (temp != null) {
            len++;
            temp = temp.next;
        }
        this.cur = head;
        return dfs(0, len-1); // still needs len, to control the base case 
    }
    private TreeNode dfs(int left, int right) {
        if (left > right) {
            return null;
        }
        int mid = (left + right)/2;

        TreeNode leftTreeNode = dfs(left, mid-1);
        TreeNode root = new TreeNode(cur.val);
        cur = cur.next;

        TreeNode rightTreeNode = dfs(mid+1, right);
        root.left = leftTreeNode;
        root.right = rightTreeNode;
        return root;
    }
}
```

## improved Solution 3&#x20;

use a class Wrapper to avoid using global variable:

```java

class Solution {
    class ListNodeWrapper {
        private ListNode node;
        ListNodeWrapper(ListNode node) {
            this.node = node;
        }
    }
    public TreeNode sortedListToBST(ListNode head) {
        int len = 0;
        ListNode temp = head;
        while (temp != null) {
            len++;
            temp = temp.next;
        }
        return dfs(new ListNodeWrapper(head), 0, len-1); // still needs len, to control the base case 
    }
    private TreeNode dfs(ListNodeWrapper cur, int left, int right) {
        if (left > right) {
            return null;
        }
        int mid = (left + right)/2;

        TreeNode leftTreeNode = dfs(cur, left, mid-1);
        TreeNode root = new TreeNode(cur.node.val);
        cur.node = cur.node.next;

        TreeNode rightTreeNode = dfs(cur, mid+1, right);
        root.left = leftTreeNode;
        root.right = rightTreeNode;
        return root;
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/tree/binary-tree-classic/109.-convert-sorted-list-to-binary-search-tree.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.