Previous Index Next

Level order traversal of binary tree

Given the root of a binary tree, display the node values at each level. Node values for all levels should be displayed on separate lines. Let’s take a look at the below binary tree.

enter image description here

Level order traversal for this tree should look like:

100
50, 200
25, 75, 350

Runtime complexity: Linear, O(n)

Memory Complexity: Linear, O(n)

Example:

Input: Tree([100, [50, 25, 75], [200, None, 350]])
Output: [[100], [50, 200], [25, 75, 350]]

Input: Tree1([10, [5, [3, 2, 4], 7], [20, 15, 35]])
Output: [[10], [5, 20], [3, 7, 15, 35], [2, 4]]

Constraints:

1<= number of nodes of the Tree <= 1000

INSTRUCTIONS

Write your code inside a function named level_order_traversal
There are no partial marks for the question.
Your function must return the output, it should not print the output.
To execute a block on the right-side coding panel, please press 'shift'+ 'enter' inside the block.
Your code should work for all permitted possible structures of the Tree.

You need to create a function with the following signature that should return an array of array. The first elements of the array would be an array containing only the top element and the last element of this array would be the array containing leaf nodes:

def level_order_traversal(root):
  result = ""
  #TODO: Write - Your - Code
  return result

Please create the Tree using the following code:

class Tree:
    def __str__(self):
        if self.left or self.right:
            return "[%s, %s, %s]" % (self.value, self.left, self.right)
        else:
            return "%s" % (self.value)
    def __repr__(self):
        return str(self)
    def __init__(self, arr):
        self.left = None
        self.right = None
        if type(arr) is list:
            self.value = arr[0]
            if arr[1]:
                self.left = Tree(arr[1])
            if arr[2]:
                self.right = Tree(arr[2])
        else:
            self.value = arr

To create the tree shown in the below image, call:

Tree([100, [50, 25, 75], [200, None, 350]])

enter image description here

See Answer

Note - Having trouble with the assessment engine? Follow the steps listed here

Data Structures and Algorithms Questions

Level order traversal of binary tree

XP

Loading comments...