How would you traverse through a binary search tree and print out each element in order?

Question

Anon · Accepted Answer

If by in order you mean InOrder traversal:
- You could traverse the tree very easily using recursion.
- If you're not explicitly allowed to use recursion.  You could use a Stack to simulate recursion
- If you're not allowed to use a Stack to simulate recursion, you could walk through the tree and "rebuild" it so that it becomes a "vine" (almost a linked list) with the nodes reordered for inorder traversal and then walk through it.

Interview Candidate · Answer

No, the interviewer did not mean inorder traversal. You have to print the elements in order as in the root first then its left element and then its right element, then the left elements right element, ect. I thought recursion would work at first too, but it doesn't because you will need to recurse all the way through either the left or right node and that's not correct. You basically have to go to the left then the right and then the left again to get its children. This can't be done using a stack either because you would get the wrong order. This problem is similar to BFS (breadth first search) - its pretty much that exact problem and that's why a queue is used.

Sigiloso · Answer

Use a queue and store all the current node's children in the queue. Loop until the queue is empty.

Amazon

Pergunta de entrevista da empresa Amazon

Respostas da entrevista

Empresas seguidas

Buscas de vagas