package org.wesome.dsalgo;
import lombok.Data;
import java.util.ArrayList;
import java.util.Objects;
public class BinarySearchTree {
Node root;
public static boolean findPath(Node node, ArrayList<Integer> arr, int end) {
/* if node is null, it means there is no path */
if (Objects.isNull(node)) {
return false;
}
arr.add(node.data);
/* if current node is the required end */
if (node.data == end) {
System.out.println("path to reach " + end + " from start is = " + arr);
return true;
}
if (end > node.data) {
return findPath(node.right, arr, end);
}
if (end < node.data) {
return findPath(node.left, arr, end);
}
System.out.println("there is no direct path to reach " + end);
return false;
}
/* Inorder -> Left -> Root -> Right */
void printInOrder() {
System.out.println("print In Order");
printInOrder(root);
}
void printInOrder(Node root) {
if (Objects.isNull(root)) {
return;
}
printInOrder(root.left);
System.out.print(" " + root.data);
printInOrder(root.right);
}
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;
}
}
@Data
class Node {
int data;
Node left, right;
public Node(int data) {
this.data = data;
left = right = null;
}
}
package org.wesome.dsalgo;
import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;
import java.util.ArrayList;
import static org.wesome.dsalgo.BinarySearchTree.findPath;
public class BinarySearchTreeTest {
@Test
void findPathTest() {
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);
Assertions.assertTrue(findPath(binarySearchTree.root, new ArrayList<>(), 7));
binarySearchTree.printInOrder();
}
}
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()
}