MerkleTree Implementation with very simple testing, implements proofPath creation and proofPath validation. Is heavily influenced by https://github.com/SimoneStefani/merkle-tree-java.

BinaryTreePrinter.java

package tech.blockchainers.crypyapi.http.common;

import org.web3j.utils.Numeric;

import java.io.PrintStream;

// taken from https://github.com/eugenp/tutorials/blob/master/data-structures/src/main/java/com/baeldung/printbinarytree/BinaryTreePrinter.java

public class BinaryTreePrinter {

    private MerkleTree tree;

    public BinaryTreePrinter(MerkleTree tree) {
        this.tree = tree;
    }

    private String traversePreOrder(MerkleTree root) {

        if (root == null) {
            return "";
        }

        StringBuilder sb = new StringBuilder();
        sb.append(Numeric.toHexString(root.root.value));

        String pointerRight = "└──";
        String pointerLeft = (root.root.right != null) ? "├──" : "└──";

        traverseNodes(sb, "", pointerLeft, root.root.left, root.root.right != null);
        traverseNodes(sb, "", pointerRight, root.root.right, false);

        return sb.toString();
    }

    private void traverseNodes(StringBuilder sb, String padding, String pointer, MerkleTree.MerkleNode node,
        boolean hasRightSibling) {

        if (node != null) {

            sb.append("\n");
            sb.append(padding);
            sb.append(pointer);
            sb.append(Numeric.toHexString(node.value));

            StringBuilder paddingBuilder = new StringBuilder(padding);
            if (hasRightSibling) {
                paddingBuilder.append("│  ");
            } else {
                paddingBuilder.append("   ");
            }

            String paddingForBoth = paddingBuilder.toString();
            String pointerRight = "└──";
            String pointerLeft = (node.right != null) ? "├──" : "└──";

            traverseNodes(sb, paddingForBoth, pointerLeft, node.left, node.right != null);
            traverseNodes(sb, paddingForBoth, pointerRight, node.right, false);

        }

    }

    public void print(PrintStream os) {
        os.print(traversePreOrder(tree));
    }

}

MerkleTree.java

package tech.blockchainers.crypyapi.http.common;

import com.google.common.primitives.Bytes;
import org.web3j.crypto.Hash;
import org.web3j.utils.Numeric;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

public class MerkleTree {

    static class ProofPathElement {

        Location location;
        byte[] value;

        public ProofPathElement(byte[] value, Location location) {
            this.location = location;
            this.value = value;
        }

        public Location getLocation() {
            return location;
        }

        public byte[] getValue() {
            return value;
        }

        @Override
        public String toString() {
            return "ProofPathElement{" +
                    "location=" + location +
                    ", value=" + Numeric.toHexString(value) +
                    '}';
        }
    }

    enum Location {
        SMALLER, BIGGER;
    }

    MerkleNode root;

    public MerkleTree(MerkleNode root) {
        this.root = root;
    }

    static class MerkleNode {
        byte[] value;
        MerkleNode left;
        MerkleNode right;
        MerkleNode parent;

        public MerkleNode(byte[] value) {
            this.value = value;
        }

        public MerkleNode(MerkleNode left, MerkleNode right) {
            this.value = Hash.sha256(Bytes.concat(left.value, right.value));
            left.parent = this;
            this.left = left;
            right.parent = this;
            this.right = right;
        }

        public List<ProofPathElement> proofPath() {
            List<ProofPathElement> proofPath = new ArrayList<>();
            return proofPath(proofPath, this);
        }

        private List<ProofPathElement> proofPath(List<ProofPathElement> proofPath, MerkleNode node) {
            List<ProofPathElement> proofPathAppend = new ArrayList<>(proofPath);
            if (node.parent == null) {
                return proofPathAppend;
            }
            if (node.parent.left == node) {
                proofPathAppend.add(new ProofPathElement(node.parent.right.value, Location.BIGGER));
                return proofPath(proofPathAppend, node.parent);
            } else if (node.parent.right == node) {
                proofPathAppend.add(new ProofPathElement(node.parent.left.value, Location.SMALLER));
                return proofPath(proofPathAppend, node.parent);
            } else {
                throw new IllegalStateException("But HOW?");
            }
        }

        public static boolean validateProofPath(MerkleNode leaf, MerkleNode root, List<ProofPathElement> elements) {
            byte[] hashedValue = leaf.value;
            for (ProofPathElement element : elements) {
                if (element.location == Location.SMALLER) {
                    hashedValue = Hash.sha256(Bytes.concat(element.value, hashedValue));
                } else {
                    hashedValue = Hash.sha256(Bytes.concat(hashedValue, element.value));
                }
            }
            return Arrays.equals(hashedValue, root.value);
        }

        @Override
        public String toString() {
            return "MerkleNode {" +
                    "value=" + Numeric.toHexString(this.value) + '}';
        }
    }

    public static MerkleNode findNode(MerkleNode current, byte[] value) {
        if (Arrays.equals(current.value, value)) {
            return current;
        } else {
            if (current.left != null) {
                MerkleNode left = findNode(current.left, value);
                if (left != null) {
                    return left;
                }
            }
            if (current.right != null) {
                MerkleNode right = findNode(current.right, value);
                if (right != null) {
                    return right;
                }
            }
            return null;
        }

    }

    public static MerkleTree createTreeFromList(List<byte[]> leaves) {
        List<MerkleNode> leavesAsNodes = leaves.stream().map(MerkleNode::new).collect(Collectors.toList());
        MerkleNode root = createRootFromNodeList(leavesAsNodes);
        return new MerkleTree(root);
    }

    private static MerkleNode createRootFromNodeList(List<MerkleNode> leaves) {
        List<MerkleNode> parents = new ArrayList<>();
        for (int i=0; i<leaves.size(); i+=2) {
            if (leaves.size() < (i+2)) {
                parents.add(new MerkleNode(leaves.get(i), new MerkleNode(new byte[]{})));
            } else {
                parents.add(new MerkleNode(leaves.get(i), leaves.get(i+1)));
            }
        }
        if (parents.size() <= 1) {
            return (parents.size() == 0) ? null : parents.get(0);
        } else {
            return createRootFromNodeList(parents);
        }
    }

}

MerkleTreeTest.java

package tech.blockchainers.crypyapi.http.common;

import org.junit.Assert;
import org.junit.jupiter.api.Test;
import org.web3j.crypto.Hash;
import org.web3j.utils.Numeric;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;

public class MerkleTreeTest {

    @Test
    public void printSampleMarkleTree() {
        MerkleTree tree = getSampleMerkleTree();
        new BinaryTreePrinter(tree).print(System.out);
    }

    @Test
    public void getMerkleTreeProofPath() {
        MerkleTree tree = getSampleMerkleTree();
        new BinaryTreePrinter(tree).print(System.out);
        MerkleTree.MerkleNode nodeNo7 = MerkleTree.findNode(tree.root, Hash.sha256(BigInteger.valueOf((long) 7).toByteArray()));
        //System.out.println("\n" + nodeNo7);
        System.out.println(nodeNo7.proofPath());
    }

    @Test
    public void validateMerkleTreeProofPath() {
        MerkleTree tree = getSampleMerkleTree();
        new BinaryTreePrinter(tree).print(System.out);
        MerkleTree.MerkleNode nodeNo7 = MerkleTree.findNode(tree.root, Hash.sha256(BigInteger.valueOf((long) 100).toByteArray()));
        //System.out.println("\n" + nodeNo7);
        List<MerkleTree.ProofPathElement> proofPath = nodeNo7.proofPath();
        Assert.true(MerkleTree.MerkleNode.validateProofPath(nodeNo7, tree.root, proofPath));
    }

    private MerkleTree getSampleMerkleTree() {
        List<byte[]> nums = new ArrayList<>();
        for (int i=0; i<100000; i++) {
            nums.add(Hash.sha256(BigInteger.valueOf((long)i).toByteArray()));
        }
        MerkleTree merkleTree = MerkleTree.createTreeFromList(nums);
        return merkleTree;
    }
}