Binary Search Trees: Given a sorted linked list into binary search tree

Problem Statement:

Given a sorted linked list into binary search tree

Example:

Input:

1 -> 2 -> 3

Output:

    2
   / \
  1   3

[[2], [1,3]]

Solution 1: Using Vector

Add linked list elements into the vector.

Then take the middle element and make it as root and recursively build BST.

Time Complexity: O(n)
Space Complexity: O(n)

Solution 2: Using fast and slow pointer

Find the middle element using fast and slow pointer.

Then do a recursively call, and construct the tree.

Time Complexity: O(n log n)
Space Complexity: O(logn)

Code Solution

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

class LL_Node 
{
public:
    int data;
    LL_Node *next;

    LL_Node (int x) 
    {
        data = x;
        next = nullptr;
    }
};

class Tree_Node 
{
public:
	int data;
	Tree_Node* left;
	Tree_Node* right;

	Tree_Node(int x) 
	{
		data = x;
		left = nullptr;
		right = nullptr;
	}
};


Tree_Node* solve(vector<int>&v,int s ,int e)
{
    if(s>e) 
    	return nullptr;

    int mid  = s+(e-s)/2;

    Tree_Node* root = new Tree_Node (v[mid]);

    root->left = solve(v,s,mid-1);

    root->right = solve(v,mid+1,e);
    
    return root;
}

Tree_Node* solution_1(LL_Node* head) 
{
    if(!head) 
    	return nullptr;

    vector<int>v;

    while(head)
    {
        v.push_back(head->data);
        head = head->next;
    }

    int start = 0;
    int end = v.size()-1;
    return solve(v, start, end);
}


Tree_Node* solution_2(LL_Node* head) 
{
    if(head == NULL) 
    	return NULL;

    if(head->next == NULL) 
    	return new Tree_Node(head->data);

    LL_Node* slow = head;
    LL_Node* fast = head;
    LL_Node* mid = slow;

    while(fast != NULL && fast->next != NULL) 
    {
        mid = slow;
        slow = slow->next;
        fast = fast->next->next;
    }

    Tree_Node* node = new Tree_Node(slow->data);

    mid->next = nullptr;
    node->left = solution_2(head);
    node->right = solution_2(slow->next);
    
    return node;
}

void display(Tree_Node* root) 
{
	if (!root) return;
	cout << root->data << " ";
	display(root->left);
	display(root->right);
}

int main() 
{
	LL_Node* head = new LL_Node(1);
	head->next = new LL_Node(2);
	head->next->next = new LL_Node(3);
	head->next->next->next = new LL_Node(4);
	head->next->next->next->next = new LL_Node(5);
	head->next->next->next->next->next = new LL_Node(6);
	head->next->next->next->next->next->next = new LL_Node(7);


	Tree_Node* root = solution_1(head);
	display(root);
    cout<<endl;
	root = solution_2(head);
	display(root);

	return 0;
}

Output

4 2 1 3 6 5 7 
4 2 1 3 6 5 7