Can any one shed light on how to solve this tree question? I was asked during my Facebook phone interview. Given a tree, the algorithm should print node values in a certain order. ______________________ A _______________ /________________\ ________ B__________________________ C _____/_______\_____________________/______\ __D__________(null)___________E___________F It should print ABD ACE ACF I came up with a solution to do that and went through each line of my code with the above input node values and verified that the code produces the desired output. After that, the interview added one more node as shown below, and said the output should be as shown below. The thing I had a difficulty with was the K value on its own on the last line while the other lines all start with root node value A. I struggled for trying to come up with an algorithm that would leave only K on the 4th iteration(pass) about several minutes and I ran out of time. ______________________ A _______________ /________________\ ________ B____________________________C _____/_______\_____________________/_______\ ___D__________(null)_____________E_____________F _/_____\______________________/_____\__________/_____\ (null)__(null)_______________(null)___(null)__(null)_______K should print ABD ACE ACF K
Print first 3 characters of output per line
This is the iterative version of dfs traversal, basically iterate upto 3 levels and start next levels as new root nodes
Where did the OP tell that every third level is a new node level? :o LC question?
That is what I would ask the interviewer as clarifications, based on the follow up output it seems that k node would become root in the output and so on
I'm confused why should it be K and not ACFK?
It seems like it was an additional constraint added after op coded the solution where he would get ACFK as the output.
Can you please post the right tree output. It's impossible to understand what the question is asking
I had the exact same problem asked last week without the k. It was easy solution. Write a depth first tree trivarsal function, with a string being appended on every node visited and add an extra if condition to only print the string if the node is leaf. I guess since it was easy they made little harder with the K.
Tech Industry
Yesterday
2971
I am starting to think Chinese interviewers currently fail non-Chinese candidates on purpose.
World Conflicts
Yesterday
565
American police seem to work only when Israel is challenged
Tech Industry
9h
2210
Asians - what are your thoughts on asian female white male ?
Software Engineering Career
3d
20004
What level would Zuck be, had he not created FB
Tech Industry
Yesterday
3909
Crossed a line with my boss
So obviously depth first traversal...and you’d need to ask more questions. Output could be wrapping after 3 characters? At least that’s what it looks like to me. Since the final traversal would be ACFK
DFS wouldn’t print root value each time though that’s easy enough to store. Can’t figure out when to print the root value based on his examples though. Thought it should print ACFK, not ACF (linebreak) K.
Depth first for each full route. If you see, the leaves are printed in depth first order. So imagine that each time you hit a leaf node, you print the entire route so far, wrapping at 3 characters. Meaning something like temp_route = route while temp_route.length > 3: ....print(temp_route[:3]) ....temp_route = temp_route[3:]