JetBrains Academy: Binary search tree in Java - Kamil-Jankowski/Learning-JAVA GitHub Wiki
JetBrains Academy: Binary search tree in Java
The height of the tree:
There is an empty binary search tree and one operation on it – node addition. A sequence of keys is given. What will be the height of the tree after adding all the keys in that order?
Input: On the first line – the number of nodes n. On the second line are keys that you need to add to the tree, divided by spaces. It is guaranteed that all the keys are different.
Output: On the first line print one number: the height of the resulting tree.
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
Integer.parseInt(scanner.nextLine());
String[] keys = scanner.nextLine().split("\\s+");
BinarySearchTree tree = new BinarySearchTree();
for (String k : keys) {
int key = Integer.parseInt(k);
int defaultValue = key;
tree.insert(key, defaultValue);
}
int rootLevel = 1;
System.out.println(tree.height() - rootLevel);
}
}
class BinarySearchTree {
private Node root;
Node insert(Node t, Node parent, int key, int value) {
if (t == null) {
t = new Node(key, value, parent);
} else {
if (key < t.key) {
t.left = insert(t.left, t, key, value);
} else {
t.right = insert(t.right, t, key, value);
}
}
return t;
}
public void insert(int key, int value) {
root = insert(root, null, key, value);
}
private int height(Node n) {
if (n == null) {
return 0;
}
return findMax(height(n.left), height(n.right)) + 1;
}
public int height() {
Node n = root;
return height(n);
}
private int findMax(int a, int b) {
if (a >= b) {
return a;
} else {
return b;
}
}
static class Node {
int key;
int value;
Node left;
Node right;
Node parent;
public Node(int key, int value, Node parent) {
this.key = key;
this.value = value;
this.parent = parent;
}
}
}
The in-order traversal:
There is an empty binary tree and three operations on it:
+ x value: add a node with the key ‘x’ and the value ‘value’;- x: delete the node with the key ‘x’;! x new: change the value of the node with the key ‘x’ to ‘new’.
Print values of the resulting tree in-order.
Input: On the first line – the number of queries n. On the following n lines there are queries of three types: + x value, - x and ! x new.
Output: On the first line print the values of the resulted tree in-order, divided by spaces.
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int lines = Integer.parseInt(scanner.nextLine());
BinarySearchTree tree = new BinarySearchTree();
int key;
int value;
for (int i = 0; i < lines; i++) {
String[] params = scanner.nextLine().split("\\s+");
String command = params[0];
switch (command) {
case "+":
key = Integer.parseInt(params[1]);
value = Integer.parseInt(params[2]);
tree.insert(key, value);
break;
case "-":
key = Integer.parseInt(params[1]);
tree.remove(key);
break;
case "!":
key = Integer.parseInt(params[1]);
value = Integer.parseInt(params[2]);
tree.changeValue(key, value);
break;
default:
System.out.println("Wrong command symbol provided. Please use: + / - / !");
break;
}
}
tree.printInOrder();
}
}
class BinarySearchTree {
private Node root;
private Node search(Node t, int key) {
if (t == null || t.key == key) {
return t;
}
if (key < t.key) {
return search(t.left, key);
} else {
return search(t.right, key);
}
}
/**
*
* @param key to be found
* @return first appearance of the key in the tree
*/
public Node search(int key) {
return search(root, key);
}
private Node insert(Node t, Node parent, int key, int value) {
if (t == null) {
t = new Node(key, value, parent);
} else {
if (key < t.key) {
t.left = insert(t.left, t, key, value);
} else {
t.right = insert(t.right, t, key, value);
}
}
return t;
}
public void insert(int key, int value) {
root = insert(root, null, key, value);
}
void replace(Node a, Node b) {
if (a.parent == null) {
root = b;
} else if (a == a.parent.left) {
a.parent.left = b;
} else {
a.parent.right = b;
}
if (b != null){
b.parent = a.parent;
}
}
private void remove(Node t, int key) {
if (t == null) {
return;
}
if (key < t.key) {
remove(t.left, key);
} else if (key > t.key) {
remove(t.right, key);
} else if (t.left != null && t.right != null) {
Node m = t.right;
while (m.left != null) {
m = m.left;
}
t.key = m.key;
t.value = m.value;
replace(m, m.right);
} else if (t.left != null) {
replace(t, t.left);
} else if (t.right != null) {
replace(t, t.right);
} else {
replace(t, null);
}
}
/**
* Removes first key found in the tree
*
* @param key of the node to be removed
*/
public void remove(int key) {
remove(root, key);
}
public void printInOrder() {
printInOrder(root);
System.out.println();
}
private void printInOrder(Node node) {
if (node == null) {
return;
}
printInOrder(node.left);
System.out.print(node.value + " ");
printInOrder(node.right);
}
public void changeValue(int key, int newValue) {
search(key).value = newValue;
}
static class Node {
int key;
int value;
Node left;
Node right;
Node parent;
public Node(int key, int value, Node parent) {
this.key = key;
this.value = value;
this.parent = parent;
}
}
}
or
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
BinarySearchTree tree = new BinarySearchTree();
int lines = Integer.parseInt(scanner.nextLine());
for (int i = 0; i < lines; i++) {
String[] params = scanner.nextLine().split("\\s+");
InputUtils.executeOperations(params, tree);
}
tree.printInOrder();
}
}
class InputUtils {
public static void executeOperations(String[] arguments, BinarySearchTree tree) {
String command = arguments[0];
Command cmd = Command.getCommandFor(command);
run(Objects.requireNonNull(cmd), tree, arguments);
}
private static <E> void run(Command command, BinarySearchTree tree, String... arguments){
command.apply(tree, arguments);
}
}
enum Command {
INSERT("+") {
@Override
public void apply(BinarySearchTree tree, String... arguments) {
int key = Integer.parseInt(arguments[1]);
int value = Integer.parseInt(arguments[2]);
tree.insert(key, value);
}
}, REMOVE("-") {
@Override
public void apply(BinarySearchTree tree, String... arguments) {
int key = Integer.parseInt(arguments[1]);
tree.remove(key);
}
}, REPLACE("!") {
@Override
public void apply(BinarySearchTree tree, String... arguments) {
int key = Integer.parseInt(arguments[1]);
int value = Integer.parseInt(arguments[2]);
tree.changeValue(key, value);
}
};
private final String command;
Command(String command) {
this.command = command;
}
public static Command getCommandFor(String symbol) {
for (Command name : values()) {
if (name.command.equals(symbol)) {
return name;
}
}
throw new IllegalArgumentException("Wrong symbol provided: " + symbol + "\n" +
"Please use following: + / - / !");
}
public abstract void apply(BinarySearchTree tree, String... arguments);
}
class BinarySearchTree {
private Node root;
private Node search(Node t, int key) {
if (t == null || t.key == key) {
return t;
}
if (key < t.key) {
return search(t.left, key);
} else {
return search(t.right, key);
}
}
/**
*
* @param key to be found
* @return first appearance of the key in the tree
*/
public Node search(int key) {
return search(root, key);
}
private Node insert(Node t, Node parent, int key, int value) {
if (t == null) {
t = new Node(key, value, parent);
} else {
if (key < t.key) {
t.left = insert(t.left, t, key, value);
} else {
t.right = insert(t.right, t, key, value);
}
}
return t;
}
public void insert(int key, int value) {
root = insert(root, null, key, value);
}
void replace(Node a, Node b) {
if (a.parent == null) {
root = b;
} else if (a == a.parent.left) {
a.parent.left = b;
} else {
a.parent.right = b;
}
if (b != null){
b.parent = a.parent;
}
}
private void remove(Node t, int key) {
if (t == null) {
return;
}
if (key < t.key) {
remove(t.left, key);
} else if (key > t.key) {
remove(t.right, key);
} else if (t.left != null && t.right != null) {
Node m = t.right;
while (m.left != null) {
m = m.left;
}
t.key = m.key;
t.value = m.value;
replace(m, m.right);
} else if (t.left != null) {
replace(t, t.left);
} else if (t.right != null) {
replace(t, t.right);
} else {
replace(t, null);
}
}
/**
* Removes first key found in the tree
*
* @param key of the node to be removed
*/
public void remove(int key) {
remove(root, key);
}
public void printInOrder() {
printInOrder(root);
System.out.println();
}
private void printInOrder(Node node) {
if (node == null) {
return;
}
printInOrder(node.left);
System.out.print(node.value + " ");
printInOrder(node.right);
}
public void changeValue(int key, int newValue) {
search(key).value = newValue;
}
static class Node {
int key;
int value;
Node left;
Node right;
Node parent;
public Node(int key, int value, Node parent) {
this.key = key;
this.value = value;
this.parent = parent;
}
}
}
The depth of the nodes:
There is an empty binary search tree. You receive two types of queries: add a node with a given key and determine the depth of the node with a given key. For each ‘depth determination’ query print the calculated depth.
Input: On the first line there is a number of queries n. On the next n lines there are queries of two types: + x that adds an element with the key x to the binary search tree and ? x that determines the depth of the vertex with the x key.
Output: For all queries of ? x type print the depth of the node with the key x in the new line. If there is no such node, print no.
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
BinarySearchTree tree = new BinarySearchTree();
int lines = Integer.parseInt(scanner.nextLine());
for (int i = 0; i < lines; i++) {
String[] params = scanner.nextLine().split("\\s+");
InputUtils.executeOperations(params, tree);
}
}
}
class InputUtils {
/**
* Method reads array of arguments, firs of which should be command to execute, latter - key and value;
* Then it passes matched command to method run for execution along with rest of arguments
*
* @param arguments - array of Strings containing command, key, value
* @param tree - on which matched command will be executed
*/
public static void executeOperations(String[] arguments, BinarySearchTree tree) {
String command = arguments[0];
Command cmd = Command.getCommandFor(command);
run(Objects.requireNonNull(cmd), tree, arguments);
}
/**
* Method runs the apply method from enum for provided command
*
* @param command to be executed
* @param tree on which we execute the command
* @param arguments to use with the command: key, value
*/
private static void run(Command command, BinarySearchTree tree, String... arguments) {
command.apply(tree, arguments);
}
}
enum Command {
INSERT("+") {
@Override
public void apply(BinarySearchTree tree, String... arguments) {
int key = Integer.parseInt(arguments[1]);
int value;
if (arguments.length < 3) {
value = 0;
} else {
value = Integer.parseInt(arguments[2]);
}
tree.insert(key, value);
}
}, REMOVE("-") {
@Override
public void apply(BinarySearchTree tree, String... arguments) {
int key = Integer.parseInt(arguments[1]);
tree.remove(key);
}
}, REPLACE("!") {
@Override
public void apply(BinarySearchTree tree, String... arguments) {
int key = Integer.parseInt(arguments[1]);
int value = Integer.parseInt(arguments[2]);
tree.changeValue(key, value);
}
}, CHECK_DEPTH("?") {
@Override
public void apply(BinarySearchTree tree, String... arguments) {
int key = Integer.parseInt(arguments[1]);
if (tree.nodeDepth(key) >= 0) {
System.out.println(tree.nodeDepth(key));
} else {
System.out.println("no");
}
}
};
private final String command;
Command(String command) {
this.command = command;
}
/**
*
* @param symbol of command
* @return Command object which value matches provided symbol
* @throws IllegalArgumentException when no symbol matches are found
*/
public static Command getCommandFor(String symbol) {
for (Command name : values()) {
if (name.command.equals(symbol)) {
return name;
}
}
throw new IllegalArgumentException("Wrong symbol provided: " + symbol + "\n" +
"Please use following: + / - / ! / ?");
}
/**
*
* @param tree to be modified by Command object
* @param arguments i.e. key and value, or just key
*/
public abstract void apply(BinarySearchTree tree, String... arguments);
}
class BinarySearchTree {
private Node root;
private Node search(Node t, int key) {
if (t == null || t.key == key) {
return t;
}
if (key < t.key) {
return search(t.left, key);
} else {
return search(t.right, key);
}
}
/**
*
* @param key to be found
* @return first appearance of the key in the tree
*/
public Node search(int key) {
return search(root, key);
}
private Node insert(Node t, Node parent, int key, int value) {
if (t == null) {
t = new Node(key, value, parent);
} else {
if (key < t.key) {
t.left = insert(t.left, t, key, value);
} else {
t.right = insert(t.right, t, key, value);
}
}
return t;
}
public void insert(int key, int value) {
root = insert(root, null, key, value);
}
void replace(Node a, Node b) {
if (a.parent == null) {
root = b;
} else if (a == a.parent.left) {
a.parent.left = b;
} else {
a.parent.right = b;
}
if (b != null){
b.parent = a.parent;
}
}
private void remove(Node t, int key) {
if (t == null) {
return;
}
if (key < t.key) {
remove(t.left, key);
} else if (key > t.key) {
remove(t.right, key);
} else if (t.left != null && t.right != null) {
Node m = t.right;
while (m.left != null) {
m = m.left;
}
t.key = m.key;
t.value = m.value;
replace(m, m.right);
} else if (t.left != null) {
replace(t, t.left);
} else if (t.right != null) {
replace(t, t.right);
} else {
replace(t, null);
}
}
/**
* Removes first key found in the tree
*
* @param key of the node to be removed
*/
public void remove(int key) {
remove(root, key);
}
public void changeValue(int key, int newValue) {
search(key).value = newValue;
}
public int nodeDepth(int key) {
int depth = 0;
Node node = search(key);
if (node == null) {
return -1;
} else {
while (node.hasParent()) {
depth++;
node = node.parent;
}
}
return depth;
}
static class Node {
int key;
int value;
int depth;
Node left;
Node right;
Node parent;
public Node(int key, int value, Node parent) {
this.key = key;
this.value = value;
this.parent = parent;
}
public boolean hasParent() {
return parent != null;
}
}
}