Find K-th Smallest Element in Binary Search Tree

package org.wesome.dsalgo;

import lombok.Data;

import java.util.Objects;

public class BinarySearchTree {
    Node root;
    static int count = 0;

    public static Node kthSmallestElement(Node root, int kthSmallestElement) {
        if (kthSmallestElement < 1) {
            System.out.println("required kth element is less then 0");
            return null;
        }
        if (Objects.isNull(root)) {
            return null;
        }

        /*  The smallest element will be present at left, so recursively keep iterating the left side until end is reached  */
        Node left = kthSmallestElement(root.left, kthSmallestElement);

        if (Objects.nonNull(left)) {
            return left;
        }
        count++;
        /*  if count has reached the required the smallest Element, then return */
        if (count == kthSmallestElement)
            return root;

        /*  check for right subtree as well */
        return kthSmallestElement(root.right, kthSmallestElement);
    }

    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 static org.wesome.dsalgo.BinarySearchTree.count;
import static org.wesome.dsalgo.BinarySearchTree.kthSmallestElement;

public class BinarySearchTreeTest {
    @Test
    void kthSmallestElementTest() {
        count = 0;
        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);
        Node kthSmallestNode = kthSmallestElement(binarySearchTree.root, 3);
        Assertions.assertEquals(3, kthSmallestNode.data);
    }

    @Test
    void kthSmallestElementTest2() {
        count = 0;
        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);
        Node kthSmallestNode = kthSmallestElement(binarySearchTree.root, 0);
        Assertions.assertNull(kthSmallestNode);
    }

    @Test
    void kthSmallestElementTest3() {
        count = 0;
        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);
        Node kthSmallestNode = kthSmallestElement(binarySearchTree.root, 6);
        Assertions.assertEquals(6, kthSmallestNode.data);
    }
}
plugins {
    id 'java'
    id "io.freefair.lombok" version "6.4.1"
}

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()
}

 

follow us on