How to find a median of tree in Typescript


typescript algorithms binary tree tree structure

Table of contents

Introduction

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:

  1. Convert the tree to an array representation
  2. Find a median value

Convert the tree to an array representation

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.

Find a median value

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.

Final code


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.

comments powered by Disqus