Garmin

  www.garmin.com
  www.garmin.com

Interview Question

Software Engineer I Interview(Student Candidate) Olathe, KS

How would you traverse a binary tree without recursion?

Answer

Interview Answer

1 Answer

1

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

Pseudocode:

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.