Decimated by data structures exam AMA

Really? Sounds like you had shitty professors then

oof i shouldve gone software engineering major, their exam was "load numbers from a file into a binary tree and print in ascending order"

Not for walking trees, dumbass. The height of the tree is proportional to the logarithm base 2 of the amount of elements (assuming balancing) so, for a 1030 element tree you shouldn't need more than 10 stack frames and for 2060, you just need one more. The difference actually gets cheaper as you add nodes.

>logarithm base 2
what the fuck is that

Okay how would you solve, say, problem 1

How would you do backtracking without recursion, aside from using your own stack?

i wuld just do it literatively with a for loop, how else

>logarithm base 2
>what the fuck is that
are you serious dude? how do you get to data structures and not know what a logarithm is?

the only time I see algorithm is in calculus and they let me use a cheat sheet for integrals because IH ave a learning disability

I'm sorry, but this means you're in data structures, and you don't have any idea what a log(n) runtime means. That's really bad. Maybe CS isn't for you.

log(n) means that for n steps of my CPU, there is log(n) time to execute them dude I know it already

lol jesus. not only is that wrong, but even if it weren't you don't know what a logarithm is, so you don't actually understand anything.

ok ill rea what is an algorithm of base 2 but can you show me a sudo code solution to the first problem because I cannot sleep

your own stack

>literatively

???

they taught us to analyze complexity of recursion, I guess that wins

design and analysis of algorithms is next semester

>recursion is evil
Weird, I was basically taught the opposite. Trying to solve iterative problems without recursion is verbose and prone to errors.

Are you the guy that refuses to use for loops instead of recursion? You better not be.

Don't listen to that meanie, just because you don't know something doesn't mean you can't learn it. (computer) science is all about learning new shit.

thangs fren

well I guess you are just stupid

1)
You can check if subtree is ordered by asking if (self.value > left.value and self.value

Nice. I'll use that as part of our job's knowledge exam.

(1) isn't right. It's a common mistake with this problem. It fails for cases like pic related because it doesn't consider nodes higher up in the tree. You have to keep track of the max/min value in the left/right subtree, respectively, and compare it to each node as you walk the tree, although this isn't the most optimal solution, it's probably the one they expect for the exam.

Attached: tree_bst.gif (259x156, 4K)

Oh, one fairly optimal, although not so space-efficient way to check if it's ordered is to just do an in-order traversal and save it to an array. Then just check if the array is sorted. O(n) and quite simple.

>couldn't learn data organization

are you 5 years old?

Err that does not check whether the number of nodes of either subtree matches.

and space-optimization for that is to only keep previous value and check if new value is >= than prev
i guess it can't get any better

>logarithm base 2
>what the fuck is that
the current state of CS undergrads. this is why you do applied math instead lads

Right, I'm talking specifically about whether it's ordered. On an exam like this, if you're really stuck, even a dumb algorithm with multiple passes for each thing you have to show that still has a good run-time is better than doing nothing, as in OP's case.

The most optimal algorithm for checking if it's ordered is this narrowing algo, and it's pretty non-trivial. I'm familiar with it cause I saw it on leetcode before.

/* Returns true if the given tree is a binary search tree
(efficient version). */
int isBST(struct node* node)
{
return(isBSTUtil(node, INT_MIN, INT_MAX));
}

/* Returns true if the given tree is a BST and its
values are >= min and data < min || node->data > max)
return 0;

/* otherwise check the subtrees recursively,
tightening the min or max constraint */
return
isBSTUtil(node->left, min, node->data-1) && // Allow only distinct values
isBSTUtil(node->right, node->data+1, max); // Allow only distinct values
}

This algorithm looks correct.

Yeah, but I can't claim credit for it. Pulled off another site.

I am not but I am not surprised that such a Jow Forumsuy exists