Convert Binary Tree to Linked Lists by Depth

Given a binary tree, design an algorithm which creates a linked list of all the nodes at each depth.

Question

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

Example:

Input: {1,2,3,4}
Output: [1->null,2->3->null,4->null]
Explanation: 
        1
       / \
      2   3
     /
    4


Input: {1,#,2,3}
Output: [1->null,2->null,3->null]
Explanation: 
    1
     \
      2
     /
    3

Analyzation

Queue

IMPORTANT PATTERN!!

All binary tree problem that relates to “LEVEL” or “DEPTH” can use this pattern.

Import a deque package and use the queue structure. (Only 1 queue & BFS algorithm) See the code below.

The Code

from collections import deque
class Solution:
    # @param {TreeNode} root the root of binary tree
    # @return {ListNode[]} a lists of linked list
    def binaryTreeToLists(self, root):
        # Write your code here
        if root is None:
            return []
        
        queue = deque([root])
        result = []
        dummy = ListNode(0)  # 0->Null
        lastNode = None
        
        while queue:
            lastNode = dummy  # initialize
            for _ in range(len(queue)):
                node = queue.popleft()
                
                lastNode.next = ListNode(node.val)  # connect
                lastNode = lastNode.next  # move
            
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            
            result.append(dummy.next)
        
        return result

Time & Space Complexity

• Time complexity: O(n). Remember that the best case of a Binary Tree is O(logn) since it is a balanced tree but the worst case is O(n) because it can skew to only one side.
• Space complexity: O(n). Remember that the space complexity is always about how many nodes there are in a Binary Tree. If the tree is well-balanced then it is O(logn) but the worst case will be O(n).