package trees;

import java.io.ByteArrayInputStream;
import java.io.ByteArrayOutputStream;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.util.Stack;

public class SerializeBinaryTree {



    /*
     * Serialize binary tree to a file and then deserialize back to tree
     * such that original and deserialized trees are identical
     *
     * Runtime Complexity:
     * Linear, O(n)
     *
     * Memory Complexity:
     * Logarithmic, O(logn)
     *
     * One approach is to perform a depth-first traversal and serialize individual nodes to the stream.
     * Use pre-order traversal here.
      *
      *
     * */

    private static class Node {
        private int data;
        private Node left, right;

        Node(int item) {
            data = item;
            left = right = null;
        }

        public int getData() {
            return data;
        }

        public Node getLeft() {
            return left;
        }

        public Node getRight() {
            return right;
        }
    }

    private Node root1;
    private static final int MARKER = Integer.MIN_VALUE;

    protected void serialize(Node node, ObjectOutputStream stream)
            throws java.io.IOException {
        if (node == null) {
            stream.writeInt(MARKER);
            return;
        }

        stream.writeInt(node.data);
        serialize(node.left, stream);
        serialize(node.right, stream);
    }



    protected Node deserialize(ObjectInputStream stream) throws java.io.IOException {
        int val = stream.readInt();
        if (val == MARKER) {
            return null;
        }

        Node node = new Node(val);
        node.left = deserialize(stream);
        node.right = deserialize(stream);
        return node;
    }


    protected void inOrderDisplay(Node root) {
        if (root == null)
            return;

        Stack<Node> stk = new Stack<>();

        while (!stk.empty() || root != null) {
            if (root != null) {
                stk.push(root);
                root = root.left;
                continue;
            }

            System.out.print(stk.peek().data + " ");
            root = stk.pop().right;
        }
    }


    protected boolean isIdentical(Node root1,
                                  Node root2) {

        if (root1 == null && root2 == null) {
            return true;
        }

        if (root1 != null && root2 != null) {
            return ((root1.data == root2.data) &&
                    isIdentical(root1.left, root2.left) &&
                    isIdentical(root1.right, root2.right));
        }

        return false;
    }


    public static void main(String[] args) {
        try{

            SerializeBinaryTree serializeBinaryTree = new SerializeBinaryTree();
            serializeBinaryTree.root1 = new Node(1);
            serializeBinaryTree.root1.left = new Node(2);
            serializeBinaryTree.root1.right = new Node(3);
            serializeBinaryTree.root1.left.left = new Node(4);
            serializeBinaryTree.root1.left.right = new Node(5);
            serializeBinaryTree.root1.right.left = new Node(6);
            serializeBinaryTree.root1.right.right = new Node(7);

            ByteArrayOutputStream byteArrayOutputStream = new ByteArrayOutputStream();
            ObjectOutputStream stream = new ObjectOutputStream(byteArrayOutputStream);
            serializeBinaryTree.serialize(serializeBinaryTree.root1, stream);
            stream.close();

            ByteArrayInputStream byteArrayInputStream = new ByteArrayInputStream(byteArrayOutputStream.toByteArray());
            ObjectInputStream  objectInputStream = new ObjectInputStream(byteArrayInputStream);

            Node deserialize = serializeBinaryTree.deserialize(objectInputStream);

            System.out.println("\nResult");
            serializeBinaryTree.inOrderDisplay(deserialize);

            System.out.println(serializeBinaryTree.isIdentical(serializeBinaryTree.root1, deserialize));

        }
        catch(Exception ex){
            ex.printStackTrace();
        }
    }
}