109 Convert sorted list to binary search tree

I added some content to my sharing post, here is the link.

It is comeback practice for me to work on the algorithm. I did work on the algorithm 3 years 4 months ago.

I chose the algorithm to give the interviewee to work on in my last mock interview on interviewing.io. This is the second time I used the algorithm, my first time is over 6 months ago. But I found out that I did not really understand the algorithm very well. All I remember is that bottom up solution will have optimal time complexity O(N), N is total number of nodes in the linked list.

I wrote the solution based on the geekforgeeks.com article: https://www.geeksforgeeks.org/sorted-linked-list-to-balanced-bst/, and then I found the article through one of Leetcode discuss, https://articles.leetcode.com/convert-sorted-list-to-balanced-binary/. So I updated my code again.

What makes an optimal solution?

I reviewed the algorithm on August 9, 2019 5:07 pm. In terms of design of the algorithm, the algorithm should be able to do minimum, and also bug free.

Given a list with ascending order, how to construct a binary search tree with height difference than one?

It is true that inorder traversal the output will be in ascending order.
It is important to set root node of tree as the middle of list, otherwise it will not keep the property of binary search tree height difference less and equal than one.

First, think about every node in the tree will be iterated as root node once. So the list of the nodes should be iterated to match the iteration of tree nodes.
Second, apply inorder traversal and the list of iteration will match tree node iteration;
Third, think about how to avoid null pointer exception, using two index position of start and end position of list to help; one iteration of the list can get the length, and it will help to measure the list is empty or not.

The goal is for me to come out the optimal solution using O(N) and be able to write the code using less than five minutes.

Keywords

binary search tree

a list in ascending order

inorder traversal - left, root, right

tree height difference less and equal to one

Every node will be root node once

Move list pointer to next once

List move matches root node of tree iteration

count the length of list

Using middle = (start + end)/2, start is 0, and end is length of list - 1; in other words, start, end are two index of list.

I like to share my C# code.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _109_convert_sorted_list_to_binary_search_tree
{
    /// <summary>
    /// review on 9/11/2018
    /// Review the blog:
    /// https://articles.leetcode.com/convert-sorted-list-to-balanced-binary/
    /// </summary>
    class Program
    {
        // Definition for singly-linked list.
        public class ListNode
        {
            public int val;
            public ListNode next;
            public ListNode(int x) { val = x; }
        }

        public class TreeNode
        {
            public int val;
            public TreeNode left;
            public TreeNode right;
            public TreeNode(int x) { val = x; }
        }

        static void Main(string[] args)
        {
            var node1 = new ListNode(1);
            var node2 = new ListNode(2);
            var node3 = new ListNode(3);
            var node4 = new ListNode(4);
            var node5 = new ListNode(5);
            var node6 = new ListNode(6);
            var node7 = new ListNode(7);

            node1.next = node2;
            node2.next = node3;
            node3.next = node4;
            node4.next = node5;
            node5.next = node6;
            node6.next = node7;

            var root = SortedListToBST(node1);
        }       

        /// <summary>
        /// The time complexity will be O(N), N is the total number of nodes in the sorted linked list.
        /// Use bottom up approach to construct the binary search tree.
        /// 
        /// </summary>
        /// <param name="head"></param>
        /// <returns></returns>
        public static TreeNode SortedListToBST(ListNode head)
        {
            if (head == null)
            {
                return null;
            }

            var iterate = head;
            int count = 0;
            while (iterate != null)
            {
                iterate = iterate.next;
                count++;
            }

            return InorderTraversalBottomUp(ref head, 0, count - 1);
        }

        /// <summary>
        /// BST inorder traversal - match the sorted linked list order
        /// In terms of constructing BST, the inorder traversal is applied. 
        /// https://articles.leetcode.com/convert-sorted-list-to-balanced-binary/
        /// </summary>
        /// <param name="start"></param>
        /// <param name="end"></param>
        /// <returns></returns>
        private static TreeNode InorderTraversalBottomUp(ref ListNode list, int start, int end)
        {
            if (start > end)
                return null;

            int middle = (start + end) / 2;

            // enforce inorder traversal - left, root, right 
            // Left
            var left = InorderTraversalBottomUp(ref list, start, middle - 1);

            // Root 
            // each node in the sorted list will be visited one by one,
            // the node will be the root node of the tree. 
            var root = new TreeNode(list.val);

            root.left = left;

            // go to next one in the sorted linked list 
            list = list.next;

            // Right
            root.right = InorderTraversalBottomUp(ref list, middle + 1, end);

            return root;
        }
    }
}

If you like my analysis and sharing, please give me an upvote. I also put all my C# algorithm together, the link is
https://github.com/jianminchen/Leetcode_Julia/tree/master/Leetcode discussion.