# Recursive BST construction using slow-fast traversal on linked list

• ``````public TreeNode sortedListToBST(ListNode head) {
return null;
ListNode prev =null;
while(fast != null && fast.next != null)
{
fast = fast.next.next;
prev =slow;
slow=slow.next;
}
TreeNode root = new TreeNode(slow.val);
if(prev != null)
prev.next = null;
else

root.right = sortedListToBST(slow.next);
return root;
}
``````

Traverse the list to get the middle element and make that the root. left side of the list forms left sub-tree and right side of the middle element forms the right sub-tree.

• This post is deleted!

• Nice explanation

• @sassin please note, this changes the list that was passed to the function which could be a dangerous side-effect

• why do we need this?
if(prev != null)
prev.next = null;
else

• @taramilktea I have the same question too.

• @AkshathaNayak IMHO, we are recursively calling sortedListToBST and we need to find the middle node every call, if we don't break the list into three parts(before middle node, middle node and after middle node), in the next recursive call when we try to find the mid node again we will end up finding the same middle node in the first part. Hope this helps.

• making this solution slightly easier to understand. here

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

}

ListNode prev = null;

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

prev.next = null;

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

return root;
}

``````

• side-effect

Could you explain that what's the "side-effect", thanks

• @jshi11 `prev.next = null` will break the original list. If caller also needs the original list, it will become dangerous.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.