Convert Roman to Integer number - Leet Code Solution
Problem Statement Roman numerals are represented by seven different symbols: I…
November 19, 2020
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
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();
q.add(node);
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.
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();
list.add(levelList);
}
levelList.add(node);
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.
Problem Statement Roman numerals are represented by seven different symbols: I…
A Binary Search tree (BST) is a data structure which has two children nodes…
This algorithm is very efficient one, and is classic example of Divide and…
This topic is one of the most common studied. When somebody started preparation…
In this post, we will see some of the frequently used concepts/vocabulary in…
Problem Statement Given a signed integer, reverse digits of an integer. Return…
In this post, we will see some of the frequently used concepts/vocabulary in…
System design interview is pretty common these days, specially if you are having…
Introduction You are given an array of integers with size N, and a number K…
Graph Topological Sorting This is a well known problem in graph world…
Problem Statement Given an array nums of n integers and an integer target, are…
Problem Statement You are given a string text of words that are placed among…