JetBrains Academy: Trees in Java - Kamil-Jankowski/Learning-JAVA GitHub Wiki
Finding the leaves of a tree:
Given a tree in the format of "parent-child" pairs. Write a program that prints the leaves of the tree in ascending order.
Input: The first line contains an integer n — the number of edges in a tree. Each of the next n lines contains two integers separated by space. Each pair of integers corresponds to an edge of a tree: the first integer is a parent, the second one is a child. The node numbered 0 is a root. It is guaranteed that the input corresponds to a correct tree.
Output: The first line should contain the number of leaves in the tree. The second line should be a sequence of these leaves in ascending order.
import java.util.*;
public class Main {
public static void main(String[] args) {
Leafs<Integer> leafs = Leafs.create();
Scanner scanner = new Scanner(System.in);
int lines = Integer.parseInt(scanner.nextLine());
int[] parents = new int[lines];
for (int i = 0; i < lines; i++) {
String[] pair = scanner.nextLine().split("\\s+");
int parent = Integer.parseInt(pair[0]);
int child = Integer.parseInt(pair[1]);
leafs.add(child);
parents[i] = parent;
}
for (int p : parents) {
leafs.remove(p);
}
System.out.println(leafs.size());
System.out.println(leafs.toString());
}
}
class Leafs<E extends Comparable<E>> {
private final Set<E> leafSet;
/**
* Method initializes new collection of leafs.
*
* @param <E> - type of leaf elements
* @return empty Leafs collection
*/
public static <E extends Comparable<E>> Leafs<E> create() {
return new Leafs<>();
}
/**
* Private constructor.
*/
private Leafs() {
leafSet = new TreeSet<>();
}
/**
* Method adds new child into the collection of leafs.
*
* @param child to be added to collection
*/
public void add(E child) {
leafSet.add(child);
}
/**
* Method removes a leaf from the collection.
*
* @param parent - element to be removed from the collection of leafs
*/
public void remove(E parent) {
leafSet.remove(parent);
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
for (E elem : leafSet) {
sb.append(elem).append(" ");
}
return sb.toString();
}
/**
*
* @return size of leafs collection
*/
public int size() {
return leafSet.size();
}
}A full binary tree:
Given a tree represented as a list of pairs of adjacent nodes. Write a program that checks whether the given tree is a full binary tree.
Input: the first line contains an integer n ≤ 100 — the number of edges in the tree. Each of the following n lines contains a pair of two integers representing an edge. The first integer is a parent node, the second one is a child. The node numbered 00 is a root. It is guaranteed that the input corresponds to a correct tree.
Output: print "yes" if the given tree is a full binary and "no" otherwise.
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int lines = Integer.parseInt(scanner.nextLine());
Map<Integer, List<Integer>> nodes = new HashMap<>();
for (int i = 0; i < lines; i++) {
String[] pair = scanner.nextLine().split("\\s+");
int parent = Integer.parseInt(pair[0]);
int child = Integer.parseInt(pair[1]);
if (nodes.containsKey(parent)) {
nodes.get(parent).add(child);
} else {
List<Integer> children = new ArrayList<>();
children.add(child);
nodes.put(parent, children);
}
}
System.out.println(TreeUtils.isFullBinaryTree(nodes) ? "yes" : "no");
}
}
class TreeUtils {
/**
* Method checks if given map represents full binary tree (all parents have exactly two children).
*
* @param map - map containing parent as a key and list of children as value;
* @param <E> - type of elements in the map;
* @return true if map is full binary tree, false otherwise;
*/
public static <E> boolean isFullBinaryTree(Map<E, List<E>> map) {
Set<E> parents = map.keySet();
boolean isFullBinary = true;
for (E parent : parents) {
if (map.get(parent).size() == 2) {
isFullBinary = true;
} else {
isFullBinary = false;
break;
}
}
return isFullBinary;
}
}The pre-order traversal:
A full ternary tree with depth n is given. Write a program that prints all nodes of the tree in Pre-Order. Enumeration starts from 0 and goes sequentially through the levels. In the picture below you can see a tree with depth 2.
Pre-order for k-ary tree is (Root, Child_1, …., Child_k).
Input: n is the depth of the tree.
Output: a sequence of nodes in Pre-Order divided by spaces.
TBDThe height of a tree (v1):
One more way to represent a tree in computer memory is to store it as an array of parents. For example, an array of parents is as follows:
NODE | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
PARENT| 1 | -1 | 5 | 1 | 0 | 1 | 5 |
The node's 3 parent is 1, thus parent[3] = 1. The node 1 is a root, hence parent[1] = -1.
Your task here is to write a program that finds the height of a tree represented in the described format. The expected time complexity of your algorithm is O(k2), where k is the number of nodes in a tree.
Input: The first line contains an integer k — the number of nodes of a tree. The next line contains k integers corresponding to an array of parents. It is guaranteed that an array represents a correct tree.
Output: The height of the input tree.
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int size = Integer.parseInt(scanner.nextLine());
String[] input = scanner.nextLine().split("\\s+");
int[] parents = new int[size];
for (int i = 0; i < size; i++) {
parents[i] = Integer.parseInt(input[i]);
}
System.out.println(TreeUtils.checkHeight(parents));
}
}
class TreeUtils {
private static int nodeDepth = 1;
/**
* Method checks depth/height of a tree from provided array of parents;
* For example:
* The node's 3 parent is 1, thus parent[3] = 1
* The node 1 is a root, hence parent[1] = -1.
*
* @param parents - array of ints with number of parent node for each index of array
* @return height of tree
*/
public static int checkHeight(int[] parents) {
int treeDepth = 0;
for (int parent : parents) {
checkParent(parent, parents);
treeDepth = Math.max(nodeDepth, treeDepth);
resetNodeDepth();
}
return treeDepth;
}
/**
* Method checks parent of provided node in parents array
*
* @param node of with parent we are checking
* @param parents - array of parents
* @return parent of the node
*/
private static int checkParent(int node, int[] parents) {
if (node == -1) {
return node;
}
nodeDepth++;
return checkParent(parents[node], parents);
}
/**
* Method resets node depth to default value.
*/
private static void resetNodeDepth() {
nodeDepth = 1;
}
}v2 - O(k)
TBD