Problem

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)

Examples

Example 1:

Input:
       1
     /   \
    2     3
  /  \   / \
 4    5 6   7

Output:
(1) => NULL
(2) => (3) => NULL
(4) => (5) => (6) => (7) => NULL

Input: root = [1,2,3,4,5,6,7]
Output: [
	[1],
	[2, 3],
	[4, 5, 6, 7],
]

Similar Problems

Populate next pointer to right node in Perfect Binary Tree

Solution

Method 1 - Level order traversal OR BFS

We just do a level-order traversal throughout the tree. Here is a queue based solution:

  • Create a List for ans
  • Do the level order traversal using queue(Breadth First Search), we will check queue size and start iterating for that level.
  • For each level, keep track of head node, and add the level
  • At end of level, add the list node

Code

Java
Returning List of ListNodes
class TreeToLinkedListAtDepth {

	public List<ListNode> levelOrderLinkedLists(TreeNode root) {
		List<ListNode> ans = new LinkedList<>();

		if (root == null) {
			return ans;
		}

		Queue<TreeNode> queue = new LinkedList<>();
		queue.add(root);

		ListNode currLevel = new ListNode(0);

		while (!queue.isEmpty()) {
			int sz = queue.size();
			// create dummy currLevel
			currLevel = new ListNode(0);
			ListNode head = currLevel;

			while (sz > 0) {
				TreeNode curr = queue.poll();
				currLevel.next = new ListNode(curr.val);
				currLevel = currLevel.next;

				if (curr.left != null) {
					queue.offer(curr.left);
				}

				if (curr.right != null) {
					queue.offer(curr.right);
				}

				sz--;
			}
			// currLevel at head has dummy 0
			ans.add(head.next);
		}

		return ans;
	}
}
Returning List of List of TreeNodes
public class TreeToLinkedListAtDepth {

	public static List <List<Integer>> createLinkedLists(TreeNode root) {
		List <List<Integer>> ans = new ArrayList<>();

		if (root == null) return ans;

		Queue<TreeNode> queue = new LinkedList<>();
		queue.offer(root);

		while (!queue.isEmpty()) {
			int levelSize = queue.size();
			List<Integer> currentLevel = new ArrayList<>();

			for (int i = 0; i < levelSize; i++) {
				TreeNode node = queue.poll();
				currentLevel.add(node.val);

				if (node.left != null) {
					queue.offer(node.left);
				}

				if (node.right != null) {
					queue.offer(node.right);
				}
			}

			ans.add(currentLevel);
		}

		return ans;
	}
}
Returning List of List of Integers
public class TreeToLinkedListAtDepth {

	public static List < List<Integer>> createLinkedLists(TreeNode root) {
		List < List<Integer>> ans = new ArrayList<>();

		if (root == null) return ans;

		Queue<TreeNode> queue = new LinkedList<>();
		queue.offer(root);

		while (!queue.isEmpty()) {
			int levelSize = queue.size();
			List<Integer> currentLevel = new ArrayList<>();

			for (int i = 0; i < levelSize; i++) {
				TreeNode node = queue.poll();
				currentLevel.add(node.val);

				if (node.left != null) {
					queue.offer(node.left);
				}

				if (node.right != null) {
					queue.offer(node.right);
				}
			}

			ans.add(currentLevel);
		}

		return ans;
	}
}

Complexity

  • ⏰ Time complexity: O(n) where n is number of nodes in tree.
  • 🧺 Space complexity: O(n) for using the queue.