Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Written Test
I actually think the algorithm described sounds more like pre-order. There is no indication that *all* nodes on the same level are traversed before nodes on the next level.
-1
after a node is processed, its children are added
think of 1,2,3,4,5,6,7
after 1, .. 2,3 are added.. when 2 is read.. 4,5 are added.. now queue has 3,4,5
now.. when three is processed, 6,7 are added... queue will now have 4,5,6,7 .. all children at same level..
hence breadth first
You're right. I didn't read carefully enough. I assumed that a node being added to the queue then caused that node to immediately be processed.
Breadth first
- Anonymous January 06, 2012