Discovering the position of an element within a tree-like structure by considering the total number of elements

Question

Discovering the position of an element within a tree-like structure by considering the total number of elements

I'm searching for a solution to create a dynamic Tree-like structure from a Flat Array.

Sample Input -> [1, 2, 3, 4, 5, 6, 7]

Currently, I can determine the number of columns and rows needed. However, I'm struggling to find a pattern for the position of each element in order to position them with proper spacing.

** During iteration I will receive column and index information

Ex1: Element number 4 will be placed in the 3rd column and 2nd row.

Ex2: If there were 3 elements in the input, the positions would be as follows:

1st element - 1st column and 2nd row

2nd element - 2nd column and 1st row

3rd element - 2nd column and 3rd row

The number of columns and rows are determined by the following method ->


getColumnLength() {
  if (this.list.length <= 1) {
    return 1;
  }
  if (this.list.length <= 3) {
    return 2;
  }
  for (let i = 2; i <= this.list.length; i++) {
    let columnLength = Math.pow(2, i);
    if (columnLength >= this.list.length) {
      return i;
    }
  }
},
getRowLength() {
  return Math.pow(2, this.getColumnLength) + 1;
},

https://i.sstatic.net/eh7oh.png

Any suggestions would be greatly appreciated.

javascript css algorithm vue.js tree

Answer 1

Answer №1

It is important to consider scenarios where the tree is not perfect, meaning the leaves are not all on the same level. In such cases, the calculation of getRowLength may be incorrect as it could count rows that remain empty. The number of rows should actually match the size of the list: each value in the list occupies its own row without any additional empty rows.

Additionally, there is a useful method called Math.clz32 that can easily determine the number of used bits in a number, which correlates well with the number of columns required.

During an in-order traversal, you can obtain the row/column information of a cell.

A demo showcasing this in-order traversal using a generator has been created. The iterator will provide position information (row and column) for the currently visited value:

const tree = {
    * iterate(index=0, column=1, cursor={row: 1}) {
        if (index >= this.list.length) return;
        yield* this.iterate(index * 2 + 1, column + 1, cursor);
        yield { index, value: this.list[index], row: cursor.row++, column };
        yield* this.iterate(index * 2 + 2, column + 1, cursor);
    },
    getColumnLength() {
        return 32 - Math.clz32(this.list.length);
    },
    displayInDOM(container) { // Demo that uses above iterate method
        container.innerHTML = `<table>${`<tr>${"<td></td>".repeat(this.getColumnLength())}<\/tr>`.repeat(this.list.length)}<\/table>`;
        const rows = container.children[0].rows;
        for (const {row, column, value} of this.iterate()) {
            rows[row - 1].cells[column - 1].textContent = value;
        }
    }
}

// Demo
tree.list = [1,2,3,4,5,6,7,8,9];
tree.displayInDOM(document.querySelector("div"));

table { border-collapse: collapse }
td { vertical-align: middle; text-align: center; min-width: 24px; border: 1px solid; }

<div></div>

Answer 2

It is important to consider scenarios where the tree is not perfect, meaning the leaves are not all on the same level. In such cases, the calculation of getRowLength may be incorrect as it could count rows that remain empty. The number of rows should actually match the size of the list: each value in the list occupies its own row without any additional empty rows.

Additionally, there is a useful method called Math.clz32 that can easily determine the number of used bits in a number, which correlates well with the number of columns required.

During an in-order traversal, you can obtain the row/column information of a cell.

A demo showcasing this in-order traversal using a generator has been created. The iterator will provide position information (row and column) for the currently visited value:

const tree = {
    * iterate(index=0, column=1, cursor={row: 1}) {
        if (index >= this.list.length) return;
        yield* this.iterate(index * 2 + 1, column + 1, cursor);
        yield { index, value: this.list[index], row: cursor.row++, column };
        yield* this.iterate(index * 2 + 2, column + 1, cursor);
    },
    getColumnLength() {
        return 32 - Math.clz32(this.list.length);
    },
    displayInDOM(container) { // Demo that uses above iterate method
        container.innerHTML = `<table>${`<tr>${"<td></td>".repeat(this.getColumnLength())}<\/tr>`.repeat(this.list.length)}<\/table>`;
        const rows = container.children[0].rows;
        for (const {row, column, value} of this.iterate()) {
            rows[row - 1].cells[column - 1].textContent = value;
        }
    }
}

// Demo
tree.list = [1,2,3,4,5,6,7,8,9];
tree.displayInDOM(document.querySelector("div"));

table { border-collapse: collapse }
td { vertical-align: middle; text-align: center; min-width: 24px; border: 1px solid; }

<div></div>

Discovering the position of an element within a tree-like structure by considering the total number of elements

Answer №1

Similar questions

How to redirect in Next.js from uppercase to lowercase url

Tips on removing properties from an object recursively according to their key/value pairs

Could someone clarify why EventEmitter leads to issues with global variables?

Why does jQuery's each function struggle to retrieve the width of hidden elements?

Differentiating between web sockets on a server

Creating Bubble Charts using npm highcharts with error code #17

What are some steps I can take to diagnose why my Express server is not receiving POST requests from my HTML form?

In WordPress, you can add a logo with accompanying text positioned at the bottom of the page

type your response here

Challenges Ahead: Navigating Vue CLI and SASS Loader Issues

Having trouble rendering a dynamic table with JavaScript utilizing a JSON object

Attempting to align two blocks side by side

Encountered an issue while trying to read properties of undefined (specifically 'meta') within a Vue 3 single-spa application

Toggle between bold and original font styles with Javascript buttons

Issue: The code is throwing an error "TypeError: Cannot read property 'push' of undefined" in the JavaScript engine "Hermes

Obtaining data from an ajax request in node.js

Encounter a problem while installing node modules

Binding arguments to child functions within Vue components

Maintaining Login State in Django REST API After Page Refresh

Tips for matching the width of tooltips with the length of the title