Sorted Link List to BST | GeeksforGeeks Problem of The Day | Leetcode 109.

Use coupon ALISHA on any GeeksforGeeks course to get 10% discount:

Join this channel to get access to perks:

Check out our other playlists:

Dynamic Programming:
Trees:
Heaps and Maps:
Arrays and Maths:
Bit Manipulation:
Greedy Algorithms:
Sorting and Searching:
Strings:

Linked Lists:
Stack and Queues:
Two Pointers:
Graphs, BFS, DFS:
Backtracking:

Non- DSA playlists:
Probability:
SQL-Basic Join functions:
SQL-Basic Aggregate functions:

[probabilitycodingisfunis]

Code CPP:
TNode* sortedListToBST(LNode *head) {
//code here
vector<int>v;
int count =0;
while(head)
{ v.push_back(head->data);
head=head->next;
count++;
}
int start = 0;
int end = count-1;
return bst(v, start, end);

}

TNode* bst(vector<int>&v, int s, int e)
{
if(s>e)return NULL;
int m = (s+e+1)/2;
TNode* temp = new TNode(v[m]);
temp->left = bst(v, s, m-1);
temp->right = bst(v, m+1, e);
return temp;
}

[unknown_coder]

Will the interviewers will be happy with this solution? Or they might ask to solve in-place?

[hrithikofficial]

in the background (aunty is in chill mode )😂

[AnkitRaj-myck]

At 9:03 you said that it is given in question that mid value should still be 3 .... I can't find that statement in question. How you get that ...☺

[lokeshthecodingguy]

very well explained one day you are definitely in one of MANG companies.

[shubamgoswami]

my concentration -> jo didi ka peeche so raha h usko dekh rah hu SAVE ME GOD

[paawansingal]

my code without using extra space for storing node values:

class Solution{
private:
LNode *findMid(LNode *head){
if(head == NULL)
return NULL;

LNode *slow = head, *fast = head;
while(fast and fast -> next){
slow = slow -> next;
fast = fast -> next -> next;
}

return slow;
}
private:
LNode *find(LNode *head, LNode *mid){
LNode *temp = head;

while(temp != NULL and temp -> next != NULL and temp -> next != mid){
temp = temp -> next;
}

temp -> next = NULL;
return head;
}
private:
TNode *buildTree(LNode *head){
if(head == NULL)
return NULL;

if(head -> next == NULL){
TNode *root = new TNode(head -> data);
root -> left = buildTree(NULL);
root -> right = buildTree(NULL);
} else {
LNode *mid = findMid(head);
LNode *secondHead = mid -> next;
LNode *firstHead = find(head, mid);

TNode *root = new TNode(mid -> data);
root -> left = buildTree(firstHead);
root -> right = buildTree(secondHead);

return root;
}


}
public:
TNode* sortedListToBST(LNode *head) {
//code here

if(head == NULL)
return NULL;

return buildTree(head);
}
};