Binary Tree

package org.wesome.ds;

import lombok.Data;

import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;

public class BinaryTree {

    void search(Node root, int search) {
        /*  null check  */
        if (Objects.isNull(root)) {
            return;
        }
        /*  recursive call  */
        if (root.data > search) {
            search(root.left, search);
        }
        if (root.data < search) {
            search(root.right, search);
        }
        /*  base case  */
        if (root.data == search) {
            System.out.println("root = " + root.data);
        }
    }

    int largest(Node root) {
        /*  null check  */
        if (Objects.isNull(root)) {
            return 0;
        }
        /*  recursive call  */
        while (Objects.nonNull(root.right)) {
            return largest(root.right);
        }
        return root.data;
    }

    int smallest(Node root) {
        /*  null check  */
        if (Objects.isNull(root)) {
            return 0;
        }
        /*  base case  */
        while (Objects.nonNull(root.left)) {
            return largest(root.left);
        }
        return root.data;
    }

    int lowestCommonAncestor(Node root, int val1, int val2) {
        /*  null check  */
        if (Objects.isNull(root)) {
            return 0;
        }
        /*  recursive call  */
        if (val1 > root.data && val2 > root.data) {
            return lowestCommonAncestor(root.right, val1, val2);
        }
        if (root.data > val1 && root.data > val2) {
            return lowestCommonAncestor(root.left, val1, val2);
        }
        return root.data;
    }

    int treeSum(Node node) {
        /*  null check  */
        if (Objects.isNull(node)) {
            return 0;
        }
        /*  base case  */
        int sum = node.data + treeSum(node.right) + treeSum(node.left);
        return sum;
    }

    void printLevelOrder(Node root) {
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            System.out.println("node = " + node.data);
            if (Objects.nonNull(node.left)) {
                queue.add(node.left);
            }
            if (Objects.nonNull(node.right)) {
                queue.add(node.right);
            }
        }
    }

    void printPreOrder(Node node) {
        /*  null check  */
        if (Objects.isNull(node)) {
            return;
        }
        /*  base case  */
        System.out.println("node = " + node.data);
        /*  recursive call  */
        printPreOrder(node.left);
        printPreOrder(node.right);
    }

    void printInOrder(Node node) {
        /*  null check  */
        if (Objects.isNull(node)) {
            return;
        }
        /*  recursive call  */
        printInOrder(node.left);
        /*  base case  */
        System.out.println("node = " + node.data);
        /*  recursive call  */
        printInOrder(node.right);
    }

    void printPostOrder(Node node) {
        /*  null check  */
        if (Objects.isNull(node)) {
            return;
        }
        /*  recursive call  */
        printPostOrder(node.left);
        /*  recursive call  */
        printPostOrder(node.right);
        /*  base case  */
        System.out.println("node = " + node.data);
    }

    void printInKeyRange(Node node, int k1, int k2) {
        /*  null check  */
        if (Objects.isNull(node)) {
            return;
        }
        /*  base case  */
        if (node.data > k1) {
            printInKeyRange(node.left, k1, k2);
        }
        if (node.data >= k1 && node.data <= k2) {
            System.out.println("node = " + node.data);
        }
        if (node.data < k2) {
            printInKeyRange(node.right, k1, k2);
        }
    }

    void printKDistance(Node node, int distance) {
        /*  null check  */
        if (Objects.isNull(node)) {
            return;
        }
        /*  base case  */
        if (0 == distance) {
            System.out.println("node = " + node.data);
        }
        /*  recursive call  */
        else {
            printKDistance(node.left, distance - 1);
            printKDistance(node.right, distance - 1);
        }
    }


    public Node mirror(Node node) {
        /*  null check  */
        if (Objects.isNull(node)) {
            return node;
        }
        /*  base case  */
        Node right = mirror(node.right);
        Node left = mirror(node.left);
        node.right = left;
        node.left = right;
        return node;
    }

    public Node insert(Node root, int data) {
        Node newNode = new Node(data);
        /*  null check  */
        if (Objects.isNull(root)) {
            return newNode;
        }
        /*  base case  */
        if (root.data > data) {
            root.left = insert(root.left, data);
        } else {
            root.right = insert(root.right, data);
        }
        return root;
    }

    public boolean identicalTree(Node a, Node b) {
        /*  null check  */
        if (Objects.isNull(a) && Objects.isNull(b)) {
            return true;
        }
        /*  base case  */
        if (a.data == b.data) {
            return true;
        }
        /*  recursive call  */
        return identicalTree(a.left, b.right) && identicalTree(a.left, b.right);
    }

    boolean isBstUtil(Node node, int min, int max) {
        /*  null check  */
        if (Objects.isNull(node)) {
            return true;
        }
        /*  base case  */
        if (node.data > min && node.data < max) {
            return true;
        }
        /*  recursive call  */
        return isBstUtil(node.left, min, node.data) && isBstUtil(node.right, node.data, max);
    }

    @Data
    public static class Node {
        int data;
        Node left, right;

        public Node(int data) {
            this.data = data;
            left = right = null;
        }
    }
}

package org.wesome.ds;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;
import org.springframework.util.Assert;

//https://www.cs.usfca.edu/~galles/visualization/BST.html
class BinaryTreeTest {


    @Test
    void mirror() {
        BinaryTree binaryTree = new BinaryTree();
        BinaryTree.Node root = null;
        root = binaryTree.insert(root, 1);
        root = binaryTree.insert(root, 2);
        root = binaryTree.insert(root, 3);
        root = binaryTree.insert(root, 4);
        System.out.println("root = " + root);
        BinaryTree.Node mirror = binaryTree.mirror(root);
        System.out.println("mirror = " + mirror);
    }

    @Test
    void printLevelOrder() {
        BinaryTree binaryTree = new BinaryTree();
        BinaryTree.Node root = null;
        root = binaryTree.insert(root, 3);
        root = binaryTree.insert(root, 1);
        root = binaryTree.insert(root, 2);
        root = binaryTree.insert(root, 4);
        binaryTree.printLevelOrder(root);
    }

    @Test
    void lowestCommonAncestor() {
        BinaryTree binaryTree = new BinaryTree();
        BinaryTree.Node root = null;
        root = binaryTree.insert(root, 3);
        root = binaryTree.insert(root, 1);
        root = binaryTree.insert(root, 2);
        root = binaryTree.insert(root, 4);
        root = binaryTree.insert(root, 6);
        root = binaryTree.insert(root, 5);
        root = binaryTree.insert(root, 10);
        root = binaryTree.insert(root, 9);
        root = binaryTree.insert(root, 11);
        Assertions.assertEquals(6, binaryTree.lowestCommonAncestor(root, 5, 11));
    }

    @Test
    void treeSum() {
        BinaryTree binaryTree = new BinaryTree();
        BinaryTree.Node root = null;
        root = binaryTree.insert(root, 1);
        root = binaryTree.insert(root, 2);
        root = binaryTree.insert(root, 3);
        root = binaryTree.insert(root, 4);
        Assertions.assertEquals(10, binaryTree.treeSum(root));
    }

    @Test
    void printPreOrder() {
        BinaryTree binaryTree = new BinaryTree();
        BinaryTree.Node root = null;
        root = binaryTree.insert(root, 1);
        root = binaryTree.insert(root, 2);
        root = binaryTree.insert(root, 3);
        root = binaryTree.insert(root, 4);
        binaryTree.printPreOrder(root);
    }

    @Test
    void printInOrder() {
        BinaryTree binaryTree = new BinaryTree();
        BinaryTree.Node root = null;
        root = binaryTree.insert(root, 1);
        root = binaryTree.insert(root, 2);
        root = binaryTree.insert(root, 3);
        root = binaryTree.insert(root, 4);
        binaryTree.printInOrder(root);
    }

    @Test
    void printPostOrder() {
        BinaryTree binaryTree = new BinaryTree();
        BinaryTree.Node root = null;
        root = binaryTree.insert(root, 1);
        root = binaryTree.insert(root, 2);
        root = binaryTree.insert(root, 3);
        root = binaryTree.insert(root, 4);
        binaryTree.printPostOrder(root);
    }

    @Test
    void largest() {
        BinaryTree binaryTree = new BinaryTree();
        BinaryTree.Node root = null;
        root = binaryTree.insert(root, 1);
        root = binaryTree.insert(root, 2);
        root = binaryTree.insert(root, 3);
        root = binaryTree.insert(root, 4);
        Assertions.assertEquals(4, binaryTree.largest(root));
    }

    @Test
    void smallest() {
        BinaryTree binaryTree = new BinaryTree();
        BinaryTree.Node root = null;
        root = binaryTree.insert(root, 1);
        root = binaryTree.insert(root, 2);
        root = binaryTree.insert(root, 3);
        root = binaryTree.insert(root, 4);
        Assertions.assertEquals(1, binaryTree.smallest(root));
    }

    @Test
    void search() {
        BinaryTree binaryTree = new BinaryTree();
        BinaryTree.Node root = null;
        root = binaryTree.insert(root, 1);
        root = binaryTree.insert(root, 2);
        root = binaryTree.insert(root, 3);
        root = binaryTree.insert(root, 4);
        binaryTree.search(root, 4);
    }

    @Test
    void printInKeyRange() {
        BinaryTree binaryTree = new BinaryTree();
        BinaryTree.Node root = null;
        root = binaryTree.insert(root, 1);
        root = binaryTree.insert(root, 2);
        root = binaryTree.insert(root, 3);
        root = binaryTree.insert(root, 4);
        binaryTree.printInKeyRange(root, 1, 4);
    }

    @Test
    void insert() {
        BinaryTree binaryTree = new BinaryTree();
        BinaryTree.Node root = null;
        root = binaryTree.insert(root, 1);
        root = binaryTree.insert(root, 2);
        root = binaryTree.insert(root, 3);
        root = binaryTree.insert(root, 4);
        System.out.println("root = " + root);
    }

    @Test
    void identicalTree() {
        BinaryTree binaryTree = new BinaryTree();
        BinaryTree.Node root = null;
        root = binaryTree.insert(root, 1);
        root = binaryTree.insert(root, 2);
        root = binaryTree.insert(root, 3);
        root = binaryTree.insert(root, 4);
        Assert.isTrue(binaryTree.identicalTree(root, root), "nodes are identical");
    }

    @Test
    void isBstUtil() {
        BinaryTree binaryTree = new BinaryTree();
        BinaryTree.Node root = null;
        root = binaryTree.insert(root, 1);
        root = binaryTree.insert(root, 2);
        root = binaryTree.insert(root, 3);
        root = binaryTree.insert(root, 4);
        Assert.isTrue(binaryTree.isBstUtil(root, Integer.MIN_VALUE, Integer.MAX_VALUE), "tree is isBstUtil");
    }

    @Test
    void printKDistance() {
        BinaryTree binaryTree = new BinaryTree();
        BinaryTree.Node root = null;
        root = binaryTree.insert(root, 1);
        root = binaryTree.insert(root, 2);
        root = binaryTree.insert(root, 3);
        root = binaryTree.insert(root, 4);
        binaryTree.printKDistance(root, 3);
    }
}

plugins {
    id 'org.springframework.boot' version '2.5.4'
    id 'io.spring.dependency-management' version '1.0.11.RELEASE'
    id 'java'
}

group = 'org.wesome'
version = '0.0.1-SNAPSHOT'
sourceCompatibility = JavaVersion.VERSION_1_8

configurations {
    compileOnly {
        extendsFrom annotationProcessor
    }
}

repositories {
    mavenCentral()
}

dependencies {
    compileOnly 'org.projectlombok:lombok'
    annotationProcessor 'org.projectlombok:lombok'
    testImplementation 'org.springframework.boot:spring-boot-starter-test'
}

test {
    useJUnitPlatform()
}