Skip to content

Instantly share code, notes, and snippets.

@kawasima
Created December 16, 2019 09:00
Show Gist options
  • Save kawasima/ff0f00510199eeb79ea8456573ecf8a2 to your computer and use it in GitHub Desktop.
Save kawasima/ff0f00510199eeb79ea8456573ecf8a2 to your computer and use it in GitHub Desktop.
How to get differences between two trees
type TreeNode = {
key: number;
children?: TreeNode[];
}
type Oyako = [ number, number ];
const tree1 : TreeNode = {
key: 1,
children: [
{
key: 2,
},
{
key: 3,
children: [
{ key: 4 }
]
}
]
}
const tree2 : TreeNode = {
key: 1,
children: [
{
key: 2,
},
{
key: 4,
children: [
{
key: 5
}
]
},
{
key: 3,
}
]
}
function toOyakoPair(tree: TreeNode) : Oyako[] {
return (tree.children || [])
.map((child: TreeNode): Oyako[] => Array.prototype.concat([[tree.key, child.key]], toOyakoPair(child)))
.reduce((ret, x) => ret.concat(x), [])
.sort((a: Oyako, b: Oyako) => a[0] - b[0] || a[1] - b[1]);
}
function includesOyako(arr: Oyako[], x: Oyako) {
return arr.find(el => el[0] == x[0] && el[1] == x[1]) !== undefined
}
function flatUniq(array: Oyako[]) : number[] {
const knownElements = new Map();
for (const elem of array.flat()) {
knownElements.set(elem, true);
}
return Array.from(knownElements.keys());
}
function diff(tree1: TreeNode, tree2: TreeNode) {
const arr1 = toOyakoPair(tree1);
const arr2 = toOyakoPair(tree2);
return {
addBranches: arr2.filter(x => !includesOyako(arr1, x)),
removeBranches: arr1.filter(x => !includesOyako(arr2, x)),
addNodes: flatUniq(arr2).filter(x => !flatUniq(arr1).includes(x)),
removeNodes: flatUniq(arr1).filter(x => !flatUniq(arr2).includes(x)),
}
}
console.log(diff(tree1, tree2));
/*
Output:
{
addBranchs: [[1,4], [4,5]],
removeBranches: [[3,4]],
addNodes: [5],
removeNodes: []
}
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment