In this post, we will write a Typescript function to find the median value of a tree.
For this task, we will have the following interface of a tree:
interface Tree {
value: number;
children?: Tree[];
}
and we will have the following data:
const tree: Tree = {
value: 10,
children: [
{
value: 20,
children: [{ value: 40 }, { value: 50 }],
},
{
value: 30,
children: [{ value: 60 }, { value: 70 }],
},
],
};
We have a main root node and all children nodes. Each child has its own nodes.
We can find a median value of a tree in 2 actions:
We can use a recursive function to convert a tree to an array. Let’s call it traverse:
function traverse(tree: Tree) {
const result = [];
result.push(tree);
const children = tree.children || [];
children.forEach((child) => {
const childResult = traverse(child);
result.push(...childResult);
});
return result;
}
This function recursively takes all values from children and organizes them into a one-dimensional array.
To find a median value we will use the following function:
function median(tree: Tree): number {
let values = traverse(tree);
values.sort((a, b) => a.value - b.value);
if (values.length % 2 === 1) {
return values[Math.floor(values.length / 2)].value;
} else {
return (
(values[values.length / 2 - 1].value + values[values.length / 2].value) /
2
);
}
}
We pass a tree and set an array of values to the values variable. Then we do ascend sort and find a median for even and odd lengths of arrays.
interface Tree {
value: number;
children?: Tree[];
}
const tree: Tree = {
value: 10,
children: [
{
value: 20,
children: [{ value: 40 }, { value: 50 }],
},
{
value: 30,
children: [{ value: 60 }, { value: 70 }],
},
],
};
function traverse(tree: Tree) {
const result = [];
result.push(tree);
const children = tree.children || [];
children.forEach((child) => {
const childResult = traverse(child);
result.push(...childResult);
});
return result;
}
function median(tree: Tree): number {
let values = traverse(tree);
values.sort((a, b) => a.value - b.value);
if (values.length % 2 === 1) {
return values[Math.floor(values.length / 2)].value;
} else {
return (
(values[values.length / 2 - 1].value + values[values.length / 2].value) /
2
);
}
}
console.log(median(tree))
The sorted array will be [10,20,30,40,50,60,70]. It means the median will be 40.