Garmin Interview Question: How would you traverse a bina... | Glassdoor

Interview Question

Software Engineer I Interview(Student Candidate) Olathe, KS

How would you traverse a binary tree without recursion?


Interview Answer

1 Answer


Just use a stack or a queue, depending on whether you want a depth-first or breadth-first search, respectively.


Enqueue the root node.
While the queue is nonempty:
     Dequeue an element. Skip if visited. Mark it as visited otherwise. Read its value.
     Do whatever you want with the value (print it, remember it elsewhere, ignore it, etc.).
     Enqueue all its immediate neighbors.
If you were searching for a specific element and you made it this far without finding it, it's not there.

nilkn on Dec 19, 2012

Add Answers or Comments

To comment on this, Sign In or Sign Up.