• Some users have recently had their accounts hijacked. It seems that the now defunct EVGA forums might have compromised your password there and seems many are using the same PW here. We would suggest you UPDATE YOUR PASSWORD and TURN ON 2FA for your account here to further secure it. None of the compromised accounts had 2FA turned on.
    Once you have enabled 2FA, your account will be updated soon to show a badge, letting other members know that you use 2FA to protect your account. This should be beneficial for everyone that uses FSFT.

Question about Binary Tree interview question

uOpt

2[H]4U
Joined
Mar 29, 2006
Messages
2,480
I just crashed and burned in a job interview on a binary tree question. I couldn't understand the interviewer (phone only, no video, no leetcode, and double non-native speakers). I wanted to look up the correct answer to the question afterwards, but with what little I remember I can't find the question in the usual collections of interview questions.

The core of the question was "under what circumstances would you not use recursion?". He went only describing how he would iterate through the right side(s) of the tree. Apparently that was different from the left side(s). He didn't say what the iteration is supposed to achieve. I really didn't get what he wanted from me.

I have a feeling that the answer includes "when the compiler does not support tail recursion", but as I said, I find no such question.

Does this ring a bell with anybody?
 
Deep tree on device with limited stack capacity ? ( I remember working on router or cable tv box in the past and using the stack was usually discouraged and code used on them like C/C++ do not tend to have TCO guarantee like you pointed out)
 
Large trees (memory pressure becomes huge), wanting space efficiency (recursion is O(h)), or you need to very specifically control the traversal (early exit on defined condition).
 
No, I brought up running out of stack space first thing, but that wasn't what he was looking for.
 
Yeah I'm not sure then. I'd have to hear the exact question and have a little more context to really put forth any other answer. I'm assuming you're searching the tree for a specific node. It's especially confusing about "iterating through the right side" unless you're making some truly gross assumptions in there.
 
Duckduckai says this about traversing just the right side of a b-tree:
"what significance is traversal of just the right side of a b-tree?"
Traversing just the right side of a B-tree is significant because it allows for efficient insertion of sequential values, minimizing the number of disk I/O operations and keeping the tree shallower. This approach helps maintain performance during data retrieval and insertion by ensuring that new entries are added in an organized manner
https://planetscale.com/blog/btrees-and-database-indexes
https://www.geeksforgeeks.org/introduction-of-b-tree-2/

How this comes in to play with recursion, idk.
 
  • Like
Reactions: uOpt
like this
Also, depending on how the rest of the interview(s) went, it's quite possible this wasn't as bad of an issue as you think :)
 
Also, depending on how the rest of the interview(s) went, it's quite possible this wasn't as bad of an issue as you think :)

It turned into a 1-question interview based on this topic. The guy wasn't particularly nice, so probably not a big loss.
 
It turned into a 1-question interview based on this topic. The guy wasn't particularly nice, so probably not a big loss.

You're always interviewing them at the same time as they're interviewing you. If they aren't clearly communicating their interview problems, they're probably not communicating anything else.
 
Back
Top