package org.wesome.dsalgo;
import lombok.Data;
import java.util.LinkedList;
import java.util.Map;
import java.util.Objects;
import java.util.Queue;
import java.util.TreeMap;
public class BinarySearchTree {
Node root;
void insert(int data) {
System.out.println("BinarySearchTree.insert data = " + data);
root = insert(root, data);
}
Node insert(Node root, int data) {
if (Objects.isNull(root)) {
Node tempNode = new Node(data);
return tempNode;
}
if (data > root.data) {
root.right = insert(root.right, data);
} else {
root.left = insert(root.left, data);
}
return root;
}
public static void topView(Node root) {
if (Objects.isNull(root)) {
return;
}
int hrzDis = 0;
TreeMap<Integer, Integer> map = new TreeMap<>();
// create a queue for level order traversal
Queue<Node> queue = new LinkedList<>();
// Assign initialized horizontal distance value to root node and add it to the queue.
root.hrzDis = hrzDis;
// add root with level 0
queue.add(root);
while (!queue.isEmpty()) {
Node tnode = queue.poll();
hrzDis = tnode.hrzDis;
// check if this is the first node for this level
if (!map.containsKey(hrzDis)) {
map.put(hrzDis, tnode.data);
}
// add left child in the queue with horizontal distance hrzDis-1.
if (Objects.nonNull(tnode.left)) {
tnode.left.hrzDis = hrzDis - 1;
queue.add(tnode.left);
}
// add right child in the queue with horizontal distance hrzDis+1.
if (Objects.nonNull(tnode.right)) {
tnode.right.hrzDis = hrzDis + 1;
queue.add(tnode.right);
}
}
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
System.out.print(entry.getValue() + " ");
}
}
}
@Data
class Node {
int data;
Node left;
Node right;
int hrzDis;
public Node(int data) {
this.data = data;
left = right = null;
}
}
package org.wesome.dsalgo;
import org.junit.jupiter.api.Test;
public class BinarySearchTreeTest {
@Test
void topViewTest() {
BinarySearchTree binarySearchTree = new BinarySearchTree();
binarySearchTree.insert(4);
binarySearchTree.insert(2);
binarySearchTree.insert(1);
binarySearchTree.insert(3);
binarySearchTree.insert(6);
binarySearchTree.insert(5);
binarySearchTree.insert(7);
binarySearchTree.topView(binarySearchTree.root);
}
}
plugins {
id 'java'
id "io.freefair.lombok" version "6.2.0"
}
group = 'org.wesome'
version = '0.0.1-SNAPSHOT'
sourceCompatibility = JavaVersion.VERSION_1_8
configurations {
compileOnly {
extendsFrom annotationProcessor
}
}
repositories {
mavenCentral()
}
dependencies {
testImplementation 'org.junit.jupiter:junit-jupiter:5.6.2'
}
test {
useJUnitPlatform()
}