Tag Archives: binary tree

Given a binary tree, create a list of all the nodes at each depth — Recursive version

Another FAQ on the programming interview.

Question

Given a binary search tree, design an algorithm which creates a linked list of all the nodes at each depth (eg, if you have a tree with depth D, you’ll have D linked lists).

Solution

Cracking the Coding Interview (4ed) (see page 126) provided a non-recursive algorithm. For me, a recursive version is neater and much easier to understand.