Sort Binary Tree by Levels using Python

The challenge

You are given a binary tree:

class Node:
    def __init__(self, L, R, n):
        self.left = L
        self.right = R
        self.value = n

Your task is to return the list with elements from tree sorted by levels, which means the root element goes first, then root children (from left to right) are second and third, and so on.

Return empty list if root is None.

Example 1 – following tree:

                 2
            8        9
          1  3     4   5

Should return following list:

[2,8,9,1,3,4,5]

Example 2 – following tree:

                 1
            8        4
              3        5
                         7

Should return following list:

[1,8,4,3,5,7]

Test cases

Test.assert_equals(tree_by_levels(None), [])
Test.assert_equals(tree_by_levels(Node(Node(None, Node(None, None, 4), 2), Node(Node(None, None, 5), Node(None, None, 6), 3), 1)), [1, 2, 3, 4, 5, 6])

The solution in Python

# Our helper function
# ..takes in `node`
def tree_iterator(node: Node):
    # create a list to loop through
    nodes = [node]
    # loop
    while nodes:
        # yield from the list
        yield from nodes
        # internal loop
        for n in nodes[:]:
            # add to list if exists
            if n.left: nodes.append(n.left)
            if n.right: nodes.append(n.right)
            # remove from teh main list loop
            nodes.remove(n)
            
# The primary function being called
# ..passes in `node`
def tree_by_levels(node):
    # return a list of values from our helper function
    # otherwise return `[]` if node is empty
    return [n.value for n in tree_iterator(node)] if node else []

Another option:

def tree_by_levels(node):
    # create a return list, and a queue to loop
    p, q = [], [node]
    # loop
    while q:
        # take the first item from the queue
        v = q.pop(0)
        # if it is not empty
        if v is not None:
            # add it's value to the return list
            p.append(v.value)
            # add the left and right nodes to the queue
            q += [v.left,v.right]
    # return the final list, otherwise return [] is empty
    return p if not node is None else []
Tags:
5 1 vote
Article Rating
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments