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