Build a Linked List For Each Layer in a Binary Tree
by Nathan LeClaire
I've been going through problems in Cracking the Coding Interview to keep my chops strong and for giggles and this one took a little bit of wrangling for me to get:
Given a binary search tree, design an algorithm which creates a linked list of all the nodes at each depth (i e , if you have a tree with depth D, youâ€™ll have D linked lists)
So a binary tree such as :
(1) / \ / \ (2) (3) / \ / \ (4) (5) (6) (7)
Will return linked lists:
(1) => NULL (2) => (3) => NULL (4) => (5) => (6) => (7) => NULL
I wrote up my solution to this in Python, and I'm going to share it with you to study and critique.
Solution
The Linked List Implementation
If you've ever seen or written a linked list implementation before, you'll probably realize there's nothing particularly brilliant or innovative about this one. Just a good oldfashioned, simple singly linked list.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 

Usage:
1 2 3 

The Binary Tree Implementation
The binary tree implementation is similarly from scratch, and simlarly simple.
1 2 3 4 5 6 7 8 9 10 

No methods, I do all of the tree manipulation by hand. This works okay for problems of this (considerably small) scale.
The Algorithm
The algorithm that I came up with is actually slightly different than what is listed as the solution in the book, and depends a bit of idiosyncracies of Python that aren't in Java (which all of the solutions from the book are written in). Namely, it uses optional arguments to avoid wrapper methods and it uses a dictionary instead of a ArrayList<LinkedList<BinaryTree>>
.
I also differ from the solution in the book in that I grab the depth of the tree once and use that to determine the linked list's index, which is slightly less efficient than the solution that they provide. If I'm not mistaken, however, the asymptotic complexity is still the same (O(n)
).
My depth function is exactly what you'd expect (recursive):
1 2 3 4 5 6 7 8 9 10 11 12 

My tree_to_linked_lists
function does a preorder traversal, adding nodes to their corresponding linked list (based on depth) in the dictionary lists
as the tree is traversed. lists
is passed into, and returned from (in its mutated state), each call to tree_to_linked_lists
.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 

This produces a result that is sort of in reverse order compared to the solution provided by the book, but it still satisfies the problem description to provide a collection of linked lists.
Conclusion
You can find the entirety of the code here.
I need to be better at data structures and algorithms. They are fun.
Until next time, stay sassy Internet.
 Nathan