# Binary Tree - Level Order Traversal

November 19, 2020

## Problem Statement

Given a Binary tree, print out nodes in level order traversal from left to right.

``````        50
/    \
80      30
/    \      \
20     40      10

# Output
# 50 80 30 20 40 10``````

## Approach-1

Use BFS (Breadth First Search) algorithm. Since, it reaches out to nodes first that are immediate neighbours.

Idea is to take a queue, keep accumulating queue for each child.

``````void bfs(Node node) {
Queue<Node> q = new Queue();

while (!q.isEmpty()) {
Node n = q.pop();
print(n);

if (n.left != null) q.add(n.left);
if (n.right != null) q.add(n.right);
}
}``````

The `Complexity` is `O(n)` as we are visiting each nodes only once.

## Approach-2

You can prepare a list of nodes at each level. We will also use DFS (Depth First Search) algorithm here.

``````void levelOrder(Node node, List<List<Node>> list, int level) {
if (node == null)
return;
List<Node> levelList = list.get(level);
if (levelList == null) {
levelList = new ArrayList();
}

levelOrder(node.left, list, level+1);
levelOrder(node.right, list, level+1);
}

List<List<Node>> list = new ArrayList();
levelOrder(root, list, 0);``````

After this, we can print the list.

The `Complexity` is `O(n)` as we are visiting each nodes only once.

## Similar Posts

### Replace all spaces in a string with %20

Problem Statement Replace all spaces in a string with ‘%20’ (three characters…

### What is Heap Data Structure

Its a tree based data structure which is a complete binary tree(all nodes have…

### Longest Substring without repeating characters - Leet Code Solution

Problem Statement Given a string, find the length of the longest substring…

### Three Sum - Leet Code Solution

Problem Statement Given an array nums of n integers, are there elements a, b, c…

### Magical usage of Bitwise operators - Get optimized solutions for many arithmatic problems

Introduction I will list some of the interesting usage of bitwise operators…

### What FAANG companies expect in their interview from candidates

Its every software engineer’s dream to work with the big FAANG companies…

## Latest Posts

### Python SMTP Email Code - How to Send HTML Email from Python Code with Authentication at SMTP Server

Introduction This post has the complete code to send email through smtp server…

### Python SMTP Email Code - Sender Address Rejected - Not Owned By User

Introduction In a normal email sending code from python, I’m getting following…

### Nodejs with MongoDB - Number of Opened Connections Keep on Increasing with Mongoose Library

Introduction In one of my app, I was using to talk to . I have used some event…

### Django Python - How to Build Docker Image and Run Web-service on Apache with Python 3.9

Introduction So you have a Django project, and want to run it using docker image…

### Python - How to Maintain Quality Build Process Using Pylint and Unittest Coverage With Minimum Threshold Values

Introduction It is very important to introduce few process so that your code and…

### Example Jenkin Groovy Pipeline Script for Building Python Projects with Git Events and Push to Artifactory

Introduction In this post, we will see a sample Jenkin Pipeline Groovy script…