I failed a phone screen with Google. It started as a simple tree traversal question. I had to print the elements in order. I did it easily using a recursive DFS. The interviewer then went on to ask me if I could implement that with BFS. I struggled a bit and asked if he meant “implement the recursive DFS iteratively”. He said no, using bfs. Is there an easy way to do an in order printout of a binary tree using bfs?
I would have struggled a bit as well. I can get a preorder with BFS and using a stack instead of a queue. But not in order. That would require a stack but it wouldn’t be BFS. I would have asked more clarifying questions as to what the interviewer was really looking for.
I did, that was part of the problem. He couldn’t understand what I was trying to ask and it wasn’t clear to me what he wanted. We never resolved that and I failed. Lesson learned. I gotta work on communicating effectively under pressure.
What company?
Google. Just added that to the description.
Now that I’ve thought about it for a bit, you could do it with a linked list of TreeNodes.
I think the intuition for this would be similar to implementing a priority queue using an array. assume this tree (square brackets represent the next level, this is a full tree I think i.e., it goes to bottom completely for 4 levels that it has) [2],[3,8],[1,9,10,4],[5,6,7,11,12,13,15,16] inorder for this is: 5,1,6,3,7,9,11,2,12,10,13,8,15,4,16 bfs for this(level order I mean) is: brackets indicate the level [2],[3,8],[1,9,10,4],[5,6,7,11,12,13,15,16] now using bfs u need to get inorder * so first get 2, and note the index of 2 * now get next level [3,8] and place them to left and right of 2(i.e., sandwich 2). also note indices of 3 and 8 now. (output so far: 3,2,8 -> removed empty spaces in array or arraylist) * now get the next level [1,9,10,4]. now place these numbers in such a way that you are sandwiching previously noted indices(i.e., 3,8). now note indices of [1,9,10,4](output is 1,3,9,2,10,8,4) * now get the last level [5,6,7,11,12,13,15,16]. now place them such that you are sandwiching previously noted indices. now output will be 5,1,6,3,7,9,11,2,12,10,13,8,15,4,16 Hope it makes sense. And most importantly hope this algorithm is actually right lmao.
I guess you can create an (x, y) coordinate representing level and horizontal offset for every node when first traversing using bfs. This (x, y) can then be used to specify a unique placement in the inorder output array.
Yeha that’s the right solution. A simpler way to think about it: // Modified BFS pseudo algorithm 1) create a regular queue and a priority queue 1.1) the PQ should sort the elements based on their level and how far left its on the tree. You can add a (row, column) count for each element. 2) do a regular BFS 2.1) every time you pop the head of the queue 2.2) if the head doesn’t have any child, print it, then pop the PQ and that will be the next in order element. 2.3) if the head have a child, add it to PQ and its children to the queue. 2.3) continue // Corner cases: 1) empty tree 2) one element tree 3) right only or left only tree branches 4) null input // time and space complexity T(NLogN) -sorting PQ with N elements S(N)
It could be done with a stack and a doubly linked list in I think 0(n) still. Not very efficient in terms of space though. Could also do it with array and sort after the fact with merge/quick sort. I have had similar questions in interviews where I’ve given the optimal solution and then they want to know the less optimal one. Not sure if this is a way to test whether you are going from memory or know what you are doing? Definitely can trip you up though.
lesson learned. I’ll be ready for that in my next interviews.
But how is that bfs?
Still think the bfs q isnt a good phone screen question, esp when clarifying qs were asked that interviewer didn't try to resolve.
Morris traversal? But that isnt bfs, so i think the q is confusing.
BFS into a sorted list, then print list?
That might work. Seems more complicated. Guess I froze because I thought there was something obviously better I was missing
This happens quite too often with me. Sometimes during interviews I miss very obvious solutions and overthink. After interview is over I will realize.