Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Create a Linked List for each depth of a Binary Search Tree
import java.util.*;
public class LinkedListForEachDepth {
public static void main(String[] args) {
Node root = new Node(12);
// ... create BST with nodes
// create our list of LinkedLists
ArrayList<LinkedList<Node>> lists = makeLinkedLists(root);
// print them
int count = 0;
for (LinkedList<Node> ll : lists) {
Iterator<Node> iter = ll.iterator();
System.out.println("Linked list " + count++);
while (iter.hasNext()) {
System.out.print(iter.next() + " ");
}
System.out.println();
}
}
public static ArrayList<LinkedList<Node>> makeLinkedLists(Node root) {
LinkedList<Node> current = new LinkedList<Node>();
LinkedList<Node> nextLevel = new LinkedList<Node>();
ArrayList<LinkedList<Node>> lists = new ArrayList<LinkedList<Node>>();
current.add(root);
while (!current.isEmpty()) {
LinkedList<Node> newLL = (LinkedList<Node>)current.clone();
lists.add(newLL);
while (!current.isEmpty()) {
Node n = current.remove();
if (n.left != null) nextLevel.add(n.left);
if (n.right != null) nextLevel.add(n.right);
}
if (current.isEmpty()) {
current = nextLevel;
nextLevel = new LinkedList<Node>();
}
}
return lists;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.