# 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);

}
}``````

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

### Container with Most Water - Leet Code Solution

Problem Statement Given n non-negative integers a1, a2, …, an , where each…

### Young Tableau problem - Cormen

Young Tableau A a X b matrix is Young Tableau if all rows(from left to right…

### Move Zeroes - Leet Code Solution

Problem Statement Given an array nums, write a function to move all 0’s to the…

In this post, we will see some of the frequently used concepts/vocabulary in…

### Add two numbers(reverse order) link list Problem - Leet Code Solution

Problem Statement You are given two non-empty linked lists representing two non…

### Leetcode - Split a String Into the Max Number of Unique Substrings

Problem Statement Given a string s, return the maximum number of unique…

## Latest Posts

### Jenkins Pipeline with Jenkinsfile - How To Schedule Job on Cron and Not on Code Commit

Introduction In this post we will see following: How to schedule a job on cron…

### How to Git Clone Another Repository from Jenkin Pipeline in Jenkinsfile

Introduction There are some cases, where I need another git repository while…

### How to Fetch Multiple Credentials and Expose them in Environment using Jenkinsfile pipeline

Introduction In this post, we will see how to fetch multiple credentials and…

### Jenkins Pipeline - How to run Automation on Different Environment (Dev/Stage/Prod), with Credentials

Introduction I have an automation script, that I want to run on different…

### Jenkinsfile - How to Create UI Form Text fields, Drop-down and Run for Different Conditions

Introduction I had to write a CICD system for one of our project. I had to…

### Java Log4j Logger - Programmatically Initialize JSON logger with customized keys in json logs

Introduction Java log4j has many ways to initialize and append the desired…