>write a program that builds a BST from a sorted array
You can't fucking do this, arrays don't have pointers between elements, you can't just do the thing
Data structures&algorithms is literally impossible
Luis Morales
Other urls found in this thread:
ocw.mit.edu
leetcode.com
cs.cornell.edu
twitter.com
Christopher Morgan
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def into_bts(arr):
if len(arr) == 1:
return Node(arr[0])
pivot = len(arr) // 2
node = Node(arr[pivot])
if len(arr[:pivot]) > 0:
node.left = into_bts(arr[:pivot])
if len(arr[pivot+1:]) > 0:
node.right = into_bts(arr[pivot+1:])
return node
sounds like simple recursive algorithm to me
Aiden Ross
Time to drop out, user. I'll be seeing you behind the counter at McD's
Jace Gomez
Just finished the course last semester. 97/100 - it's easy
Sebastian Long
>going to McDonald's
Fat fuck. Can hear the twinkies in your post.
Isaac Gray
I literally work for mcdonalds dude
oh man pleeeeeeeease please write it in c++
Bentley Scott
wtf ? a BST stored as in an array typically has the root starting at index 0, with the children of the root at index 1 and 2, etc.. there’s a formula for it.
Owen Morris
You're thinking of heaps
Adam Brown
there isn't any difference allocate the node as std::unique_ptr
Jonathan Foster
But what is into_bits() and how does it work? Bitwise operations?
Owen Jones
typo, should have been into_bst()
Aaron Thompson
I'm a bit confused, because it sounds really simple - am I missing something?
is the problem simply to construct the BST? so for an array [1, 2, 3, 4] the resulting tree should look like:
3 (root)
3 -> 2
3 -> 4
2 -> 1
if that's the case you should really work harder at this ... that's beginner tier stuff. write a recursive function that takes the middle of an array and makes that the root, calling itself on both resulting sub arrays until you're done
Caleb Kelly
Just build a tree and then balance it dummy.
Brayden Jackson
Have you ever tried Googling this shit? I found all the code you needed plus explanations on how it works.
Jordan Evans
How the fuck did you figure this out, why can't I just insert the elements one by one, theyre already sorted
Benjamin Phillips
you could do it that way - I just go for recursive solutions whenever they apply, because the code is generally more elegant and often more efficient
an iterative approach would construct a BST from the length of the array and then go through the array to fill it. although, since you'd have to prefill it with array index values you could just straight go for the actual values instead.
I'd favor elegance over performance on anything that's still O(n) though
Zachary Cooper
>entry level class is hard
Kill yourself faggot
Brayden Anderson
Not OP but that wouldn't work, it would not produce a *balanced* search tree.
Christian Rogers
What's the best data structure/algo intro?
inb4 CLRS
Chase Barnes
well... there is CLRS, "Algorithms" and and "Algorithms, Etc."
or tons of random textbooks
Daniel Scott
Robert Evans
oh, well, it seems I need to take a discrete mathematics class first.
Aaron Brown
It's okay, it's usually first or second semester
Liam Thomas
You have to scramble it else it's just going to be a diagonal linked list
Thomas Kelly
> It's a Jow Forums does some kid's homework thread
Ryder Robinson
Xavier Wright
> Can't do a simple Leetcode/HackerRank problem
Is this why 95% of the interviewees my company interviews fail FizzBuzz and finding the longest word in a space delimited sentence?
Gabriel Bennett
Remind me what a BST is, I've been in industry too long :(
John White
>in any industry
>not knowing babbys first trees
No sir.
Joshua Watson
McDonald's doesn't sell Twinkies
Nathan Hughes
I'm drunk, don't even know what you're referencing, and I'm going to guess Binary Search Tree
Jace Sanchez
>A binary search tree (BST) is a binary tree with the following representation invariant:
>For any node n, every node in the left subtree of n has a value less than n's value, and every node in the right subtree of n has a value greater than n's value.
There is your specification to test for, if your test passes, you have a BST.
Now to balance the tree: cs.cornell.edu
>To help enforce the invariant, we color each node of the tree either red or black. Where it matters, we consider the color of an empty tree to be black. The following is added as rules to the BST invariant:
>There are no two adjacent red nodes along any path.
>Every path from the root to a leaf has the same number of black nodes. This number is called the black height (BH) of the tree.
Now build something that passes that test, filling it with data from your array. Congrats you built a red-black tree.
Gabriel Brown
>you can't do this
like just google what a binary search tree is dude. I got nearly 100% in that class.
Mason Carter
>You can't fucking do th-
YEAH ILL TAKE A NUMBER 2, NUMBER 6, LARGE COKE AN-
Dominic Williams
And what? Finish your order, faggot.
Nicholas Long
If you did that it would be extremely unbalanced and defeat the point of a Binary Tree. It would be a linked list basically. Just make the middle value the root.
Justin James
--SHUT UP IM TRYING TO ORDER. YEAH SORRY CAN YOU MAKE THAT A NUMBER 4 INSTEAD? AND CHANGE THE LARGE COKE TO A SMALL DR PEPPER.
Wyatt Parker
#include
#include
struct node{
int value;
struct node *right;
struct node *left;
};
struct node* newNode(int value){
struct node* node = (struct node*)malloc(sizeof(struct node));
node->value = value;
node->left = NULL;
node->right= NULL;
return(node);
};
struct node * add(int value, struct node *root)
{
if(root==NULL){
return newNode(value);
}
if(root->value < value){
root->right = add(value,root->right);
} else {
root->left = add(value,root->left);
}
return root;
}
int show(struct node *n){
printf("%i \n",n->value);
if(n->left != NULL){
show(n->left);
}
if(n->right != NULL){
show(n->right);
}
}
int main(int argc, char **argv) {
struct node *root = newNode(50);
for(int i = 0; i
Jackson Lewis
>can't even make a BST
Just drop out, user. CS isn't for everyone.