import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class ConcurrentBinaryTree {
    private Node root;

    static class Node {
        int value;
        Node left;
        Node right;
        final Lock lock;

        Node(int value) {
            this.value = value;
            this.left = null;
            this.right = null;
            this.lock = new ReentrantLock();
        }

        void insert(int value) {
            lock.lock();
            try {
                if (value < this.value) {
                    if (this.left == null) {
                        this.left = new Node(value);
                    } else {
                        this.left.insert(value);
                    }
                } else {
                    if (this.right == null) {
                        this.right = new Node(value);
                    } else {
                        this.right.insert(value);
                    }
                }
            } finally {
                lock.unlock();
            }
        }

        void inOrderTraversal() {
            if (this.left != null) {
                this.left.inOrderTraversal();
            }
            System.out.print(this.value + " ");
            if (this.right != null) {
                this.right.inOrderTraversal();
            }
        }
    }

    public void insert(int value) {
        if (root == null) {
            synchronized (this) {
                if (root == null) {
                    root = new Node(value);
                    return;
                }
            }
        }
        root.insert(value);
    }

    public void inOrderTraversal() {
        if (root != null) {
            root.inOrderTraversal();
        }
    }

    // Usage Example
    public static void main(String[] args) throws InterruptedException {
        ConcurrentBinaryTree tree = new ConcurrentBinaryTree();

        Thread[] threads = new Thread[7];
        int[] values = {5, 3, 7, 2, 4, 6, 8};
        for (int i = 0; i < threads.length; i++) {
            int val = values[i];
            threads[i] = new Thread(() -> tree.insert(val));
            threads[i].start();
        }

        for (Thread thread : threads) {
            thread.join();
        }

        System.out.println("In-order traversal of the binary tree:");
        tree.inOrderTraversal();
    }
}