Wix Technical Task (Jul 2019)

output.txt

$ tsc --target es6 --module commonjs wix.ts && node wix.js

---serialize---
13,A,9,12;9,B,5,8;5,C,0,4;0,0,0,0;4,E,1,2;1,0,0,0;2,0,0,0;8,P,5,6;5,0,0,0;6,0,0,0;12,G,9,10;9,0,0,0;10,0,0,0
---deserialize---
BinaryTree {
  root: BinaryNode {
    value: 'A',
    left: BinaryNode { value: 'B', left: [BinaryNode], right: [BinaryNode] },
    right: BinaryNode { value: 'G', left: null, right: null }
  },
  id: 0
}

solution.ts

interface IBinaryNode {
    value: string;
    left: IBinaryNode | null;
    right: IBinaryNode | null;
}

interface IBinaryTree {
    root: IBinaryNode;
    id: number;
    serialize: (node: IBinaryNode | null) => { id: number, str: string };
    deserialize: (str: string) => IBinaryTree;
}

class BinaryNode implements IBinaryNode {
    value: string;
    left: IBinaryNode | null;
    right: IBinaryNode | null;

    constructor(value: string, left: IBinaryNode | null, right: IBinaryNode | null) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}

class BinaryTree implements IBinaryTree {
    root: IBinaryNode;
    id: number;

    constructor(root: IBinaryNode) {
        this.root = root;
        this.id = 0;
    }

    serialize(node: IBinaryNode | null): { id: number, str: string } {
        if (node === null) {
            let id = this.id++;
            return { id, str: `${id},0,0,0` }
        }

        let { id: leftId, str: leftStr } = this.serialize(node.left);
        let { id: rightId, str: rightStr } = this.serialize(node.right);
        let id = ++this.id;
        return {
            id,
            str: `${id},${node.value},${leftId},${rightId};${leftStr};${rightStr}`
        };
    }

    deserialize(str: string): IBinaryTree {
        let nodes: Map<number, IBinaryNode> = new Map();
        let nodesStr = str.split(';');
        let reversedNodesStr = nodesStr.reverse();

        for (const nodeStr of reversedNodesStr) {
            const [id, value, left, right] = nodeStr.split(',');

            let leftNode;
            if (+left === 0) {
                leftNode = null;
            } else {
                leftNode = nodes.get(+left);
            }

            let rightNode;
            if (+right === 0) {
                rightNode = null;
            } else {
                rightNode = nodes.get(+right);
            }

            let node;
            if (+value === 0) {
                node = null;
            } else {
                node = new BinaryNode(value, leftNode, rightNode);
            }

            nodes.set(+id, node);
        }

        return new BinaryTree(nodes.get(nodesStr.length));
    }
}


// Test
const tree = new BinaryTree(
    new BinaryNode(
        "A",
        new BinaryNode(
            "B",
            new BinaryNode("C", null, new BinaryNode("E", null, null)),
            new BinaryNode("P", null, null)
        ),
        new BinaryNode("G", null, null)
    )
);

const serializedString = tree.serialize(tree.root).str;
console.log("---serialize---");
console.log(serializedString);
console.log("---deserialize---");
console.log(tree.deserialize(serializedString));