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.
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 old-fashioned, simple singly linked list.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
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 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
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 (
My depth function is exactly what you'd expect (recursive):
1 2 3 4 5 6 7 8 9 10 11 12
tree_to_linked_lists function does a pre-order 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
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.
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.