## Approach 1: Recursion

• Time:O(n\log n)
• Space:O(\log n)

## C++

``````class Solution {
public:
return nullptr;

TreeNode* root = new TreeNode(mid->val);
root->right = sortedListToBST(mid->next);

return root;
}

private:
ListNode* prev = nullptr;

while (fast && fast->next) {
prev = slow;
slow = slow->next;
fast = fast->next->next;
}
prev->next = nullptr;

return slow;
}
};
``````

## JAVA

``````class Solution {
return null;

TreeNode root = new TreeNode(mid.val);
root.right = sortedListToBST(mid.next);

return root;
}

ListNode prev = null;

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

return slow;
}
}
``````

## Python

``````class Solution:
def sortedListToBST(self, head: ListNode) -> TreeNode:
prev = None

while fast and fast.next:
prev = slow
slow = slow.next
fast = fast.next.next
prev.next = None

return slow

return None

root = TreeNode(mid.val)
root.right = self.sortedListToBST(mid.next)

return root
``````

• Time:O(n)
• Space:O(n)

## C++

``````class Solution {
public:
vector<int> A;

// construct the array
for (ListNode* curr = head; curr; curr = curr->next)
A.push_back(curr->val);

return helper(A, 0, A.size() - 1);
}

private:
TreeNode* helper(const vector<int>& A, int l, int r) {
if (l > r)
return nullptr;

const int m = (l + r) / 2;
TreeNode* root = new TreeNode(A[m]);
root->left = helper(A, l, m - 1);
root->right = helper(A, m + 1, r);
return root;
}
};
``````

## JAVA

``````class Solution {
List<Integer> A = new ArrayList<>();

// construct the array
for (ListNode curr = head; curr != null; curr = curr.next)

return helper(A, 0, A.size() - 1);
}

private TreeNode helper(List<Integer> A, int l, int r) {
if (l > r)
return null;

final int m = (l + r) / 2;
TreeNode root = new TreeNode(A.get(m));
root.left = helper(A, l, m - 1);
root.right = helper(A, m + 1, r);
return root;
}
}
``````

## Python

``````class Solution:
def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
A = []

# construct the array
while curr:
A.append(curr.val)
curr = curr.next

def helper(l: int, r: int) -> Optional[TreeNode]:
if l > r:
return None

m = (l + r) // 2
root = TreeNode(A[m])
root.left = helper(l, m - 1)
root.right = helper(m + 1, r)
return root

return helper(0, len(A) - 1)
``````

## Approach 3: Inorder Simulation

• Time:O(n)
• Space:O(\log n)

## C++

``````class Solution {
public:
}

private:

TreeNode* helper(int l, int r) {
if (l > r)
return nullptr;

const int m = (l + r) / 2;

// simulate inorder traversal: recursively form the left half
TreeNode* left = helper(l, m - 1);

// once left half is traversed, process the current node
root->left = left;

// maintain the invariance

// simulate inorder traversal: recursively form the right half
root->right = helper(m + 1, r);
return root;
}

int length = 0;
for (ListNode* curr = head; curr; curr = curr->next)
++length;
return length;
}
};
``````

## JAVA

``````class Solution {
}

private TreeNode helper(int l, int r) {
if (l > r)
return null;

final int m = (l + r) / 2;

// simulate inorder traversal: recursively form the left half
TreeNode left = helper(l, m - 1);

// once left half is traversed, process the current node
root.left = left;

// maintain the invariance

// simulate inorder traversal: recursively form the right half
root.right = helper(m + 1, r);

return root;
}

int length = 0;
for (ListNode curr = head; curr != null; curr = curr.next)
++length;
return length;
}
}
``````

## Python

``````class Solution:
def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
def helper(l: int, r: int) -> Optional[TreeNode]:
if l > r:
return None

m = (l + r) // 2

# simulate inorder traversal: recursively form the left half
left = helper(l, m - 1)

# once left half is traversed, process the current node
root.left = left

# maintain the invariance

# simulate inorder traversal: recursively form the right half
root.right = helper(m + 1, r)
return root