A Binary Search Tree
or BST
never allows a duplicate element, A Relaxed Binary Search Tree
or RBST
is a type of Binary Search Tree
that allows for duplicate elements
. It still follows the rule of Binary Search Tree
ie smaller elements
should be on the left
of the root
and larger elements
should be on the right
of the root
. To Check Binary Tree
is Relaxed Binary Search Tree keep iterating the nodes
and make sure the left
should be less
and the right
should be greater
than root
package org.wesome.dsalgo;
import lombok.Data;
import java.util.Objects;
public class BinarySearchTree {
Node root;
boolean isRelaxedBinarySearchTree(Node node, int min, int max) {
if (node == null) {
System.out.println("the root is null");
return true;
}
/* Node value should always be greater than min and smaller then maximum */
if (node.data < min || node.data > max) {
return false;
}
/* Recursively checks the left and right subtrees */
return (isRelaxedBinarySearchTree(node.left, min, node.data) && isRelaxedBinarySearchTree(node.right, node.data, max));
}
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.Test;
import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertFalse;
import static org.junit.jupiter.api.Assertions.assertNotNull;
import static org.junit.jupiter.api.Assertions.assertNull;
import static org.junit.jupiter.api.Assertions.assertTrue;
public class BinarySearchTreeTest {
@Test
void testInsertSingleElement() {
BinarySearchTree binarySearchTree = new BinarySearchTree();
binarySearchTree.insert(10);
assertNotNull(binarySearchTree.root);
assertEquals(10, binarySearchTree.root.data);
}
@Test
void testInsertMultipleElements() {
BinarySearchTree binarySearchTree = new BinarySearchTree();
binarySearchTree.insert(10);
binarySearchTree.insert(5);
binarySearchTree.insert(15);
assertEquals(10, binarySearchTree.root.data);
assertEquals(5, binarySearchTree.root.left.data);
assertEquals(15, binarySearchTree.root.right.data);
}
@Test
void testIsValidBST() {
BinarySearchTree binarySearchTree = new BinarySearchTree();
binarySearchTree.insert(10);
binarySearchTree.insert(5);
binarySearchTree.insert(15);
binarySearchTree.insert(3);
binarySearchTree.insert(7);
assertTrue(binarySearchTree.isRelaxedBinarySearchTree(binarySearchTree.root, Integer.MIN_VALUE, Integer.MAX_VALUE));
}
@Test
void testIsBSTWithEmptyTree() {
BinarySearchTree binarySearchTree = new BinarySearchTree();
assertTrue(binarySearchTree.isRelaxedBinarySearchTree(null, Integer.MIN_VALUE, Integer.MAX_VALUE));
}
@Test
void testInvalidBST() {
BinarySearchTree binarySearchTree = new BinarySearchTree();
Node root = new Node(10);
root.left = new Node(5);
root.right = new Node(8);
assertFalse(binarySearchTree.isRelaxedBinarySearchTree(root, Integer.MIN_VALUE, Integer.MAX_VALUE));
}
@Test
void testInsertDuplicateValues() {
BinarySearchTree binarySearchTree = new BinarySearchTree();
binarySearchTree.insert(10);
binarySearchTree.insert(10);
assertEquals(10, binarySearchTree.root.data);
assertNull(binarySearchTree.root.right);
}
@Test
void isRelaxedBinarySearchTreeTest() {
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.insert(7);
assertTrue(binarySearchTree.isRelaxedBinarySearchTree(binarySearchTree.root, Integer.MIN_VALUE, Integer.MAX_VALUE));
}
}
plugins {
id("java")
id("io.freefair.lombok") version "8.13"
}
group = "org.wesome.dsalgo"
version = "1.0-SNAPSHOT"
repositories {
mavenCentral()
}
dependencies {
testImplementation(platform("org.junit:junit-bom:5.10.0"))
testImplementation("org.junit.jupiter:junit-jupiter")
}
tasks.test {
useJUnitPlatform()
}
Complexity Analysis
-
Time Complexity is O(N) because each node is visited once
-
Space Complexity is O(N) For storing nodes