Recursive BST construction using slow-fast traversal on linked list


  • 44
    S
    public TreeNode sortedListToBST(ListNode head) {
        if(head == null)
            return null;
        ListNode fast = head;
        ListNode slow = head;
        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
            head  = null;
            
        root.left = sortedListToBST(head);
        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.


  • 0
    This post is deleted!

  • -1
    R

    Nice explanation


  • 3
    G

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


  • 1
    T

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


  • 0
    A

    @taramilktea I have the same question too.


  • 2
    E

    @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.


  • 3
    O

    making this solution slightly easier to understand. here

        public TreeNode sortedListToBST(ListNode head) {
            if(null == head){
                return null;
            }
            
            if(null == head.next){
                return new TreeNode(head.val);
            }
            
            ListNode prev = null;
            ListNode slow = head;
            ListNode fast = head;
            
            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.left = sortedListToBST(head);
            root.right = sortedListToBST(slow.next);
            
            return root;
        }
    
    

  • 0
    J

    @gudnm said in Recursive BST construction using slow-fast traversal on linked list:

    side-effect

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


Log in to reply
 

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