How to write a function to navigate through a non-binary tree?

Question

I have a company organisation chart I built in React/Nextjs using the 'react-organizational-chart' npm package.

I would like the user to be able to navigate up/down and side to side on the non-binary tree with either their keyboard keys, on screen buttons or both.

So for example the user might move from 'Sarah' -> 'Michael' -> 'Robert' -> 'Emily' -> 'Daniel' -'Sophie'

Please see image below for visual representation.

When moving into a new node group the user would always want to start on the first node in that group.

Here is an example of the data that is being rendered in the screenshot.

The user would also be able to go back up the tree and down the other side.

A representation of how the function should work starting from 'Sarah' 5555

navigateHierarchy('downKey') // 5556 (Michael Davis's id )
navigateHierarchy('rightKey') // 5560 (Robert Smith's id )
navigateHierarchy('downKey') // 5561 (Emily Wilson's id )
navigateHierarchy('rightKey') // 5561 (Daniel Brown's id )
navigateHierarchy('rightKey') // 5563 (Daniel Brown's id )

const data: IHierarchyData = [
  {
    name: "Sarah Johnson",
    position: "CEO",
    email: "[email protected]",
    id: "5555",
    children: [
      {
        name: "Michael Davis",
        position: "CFO",
        email: "[email protected]",
        id: "5556",
        children: [
          {
            name: "Sophia Adams",
            position: "Finance Manager",
            email: "[email protected]",
            id: "5557",
            children: [],
          },
          {
            name: "William Harris",
            position: "Financial Analyst",
            email: "[email protected]",
            id: "5558",
            children: [],
          },
          {
            name: "Oliver Turner",
            position: "Accounting Manager",
            email: "[email protected]",
            id: "5559",
            children: [],
          },
        ],
      },
      {
        name: "Robert Smith",
        position: "COO",
        email: "[email protected]",
        id: "5560",
        children: [
          {
            name: "Emily Wilson",
            position: "VP of Operations",
            email: "[email protected]",
            id: "5561",
            children: [],
          },
          {
            name: "Daniel Brown",
            position: "Director of Production",
            email: "[email protected]",
            id: "5562",
            children: [],
          },
          {
            name: "Sophie Turner",
            position: "Director of Logistics",
            email: "[email protected]",
            id: "5563",
            children: [],
          },
          {
            name: "Olivia Lee",
            position: "VP of HR",
            email: "[email protected]",
            id: "5564",
            children: [
              {
                name: "Ethan Miller",
                position: "HR Manager",
                email: "[email protected]",
                id: "5565",
                children: [],
              },
            ],
          },
        ],
      },
    ],
  },
];

The below is an early idea I had to traverse the tree using a coordinate object with x and y props.

x would represent the row you're in and y would represent the column.

I have tried writing a function that whenever the user clicks left, right, up or down it would increase the column or row respectively.

So these keyboard clicks (down, right, down) would end up with the below, but with those numbers/coords I don't think it's particularly easy or even possible to end up on 'Emily Wilson'

coords = {
    x: 2,
    y: 1,
}

How can I solve this problem?

where do you go from emily by left key - is the target now sopie or oliver? — Nina Scholz
– Nina Scholz, Commented Nov 4, 2023 at 9:32
Hi, left from Emily would get you to Oliver. However the ability to switch between sub groups isn't essential. Just being able to be able to get into a sub group and horizontally would be great haha. — daniel blythe
– daniel blythe, Commented Nov 4, 2023 at 9:53
Navigating the tree consists of two parts: (1) Given the current node, plus a direction, determine the new current node. (2) Visualize the current node. Is your problem with (1) or (2)? Your mention of coordinates makes me believe the problem is (2), but I doubt that x/y coordinates are a good identifier of a node in a tree. — Heiko Theißen
– Heiko Theißen, Commented Nov 4, 2023 at 10:09
Hello, my problem is number (1), I can handle the visualisation as long as I can get the employee id back from whatever the current node is. The tree is javascript/React, but that isn't all that important. — daniel blythe
– daniel blythe, Commented Nov 4, 2023 at 10:14

trincot · Accepted Answer · 2023-11-04 21:12:47Z

Here is a Cursor class that takes the graph as input, and which keeps track of where it is in that tree:

class Cursor {
    #data
    #path
    #current
    
    constructor(data) {
        this.#data = data;
        this.#path = [{ children: data }];
        this.#current = data[0];
    }
    get() {
        return this.#current;
    }
    down() {
        if (this.#current?.children?.length) {
            this.#path.push(this.#current);
            this.#current = this.#current.children[0];
        }
    }
    up() {
        if (this.#path.length > 1) {
            this.#current = this.#path.pop();
        }
    }
    right() {
        this.#current = this.#path.at(-1)?.children?.[this.getChildIndex() + 1] ?? this.#current;
    }
    left() {
        this.#current = this.#path.at(-1)?.children?.[this.getChildIndex() - 1] ?? this.#current;
    }
    getChildIndex() {
        if (!this.#path.length) return 0;
        let i = this.#path.at(-1).children.indexOf(this.#current);
        if (i < 0) throw "Inconsistency";
        return i;
    }
}

// Example data

const data = [{name: "Sarah Johnson",position: "CEO",email: "[email protected]",id: "5555",children: [{name: "Michael Davis",position: "CFO",email: "[email protected]",id: "5556",children: [{name: "Sophia Adams",position: "Finance Manager",email: "[email protected]",id: "5557",children: [],},{name: "William Harris",position: "Financial Analyst",email: "[email protected]",id: "5558",children: [],},{name: "Oliver Turner",position: "Accounting Manager",email: "[email protected]",id: "5559",children: [],},],},{name: "Robert Smith",position: "COO",email: "[email protected]",id: "5560",children: [{name: "Emily Wilson",position: "VP of Operations",email: "[email protected]",id: "5561",children: [],},{name: "Daniel Brown",position: "Director of Production",email: "[email protected]",id: "5562",children: [],},{name: "Sophie Turner",position: "Director of Logistics",email: "[email protected]",id: "5563",children: [],},{name: "Olivia Lee",position: "VP of HR",email: "[email protected]",id: "5564",children: [{name: "Ethan Miller",position: "HR Manager",email: "[email protected]",id: "5565",children: [],},],},],},],},];

const cursor = new Cursor(data);

// I/O

const [up, left, right, down] = document.querySelectorAll("button");
const out = document.querySelector("span");
const output = () => out.textContent = cursor.get().id;

up.addEventListener("click", () => output(cursor.up()));
left.addEventListener("click", () => output(cursor.left()));
right.addEventListener("click", () => output(cursor.right()));
down.addEventListener("click", () => output(cursor.down()));

output(cursor);

<table>
<tr><td></td><td><button>up</button></td></tr>
<tr><td><button>left</button></td><td><span></span></td><td><button>right</button></td></tr>
<tr><td></td><td><button>down</button></td></tr>
</table>

Hi @trincot, does this solution follow any kind of design pattern that I can do some reading on? Thank you.
You can read about cursors, which is a concept from databases. Usually, one can navigate back and forth with a cursor, or go to one of the extreme ends of the collection. But as here the collection is not one-dimensional, this "cursor" allows to move up/down and left/right, instead of the usual next/previous. This could also be called a four-way iterator. The implementation of the cursor here uses OOP (object oriented programming).

Heiko Theißen · Accepted Answer · 2023-11-04 10:57:21Z

I suggest enriching the data structure with up, down, left and right links and following these links when executing a navigation step.

The recursive function link below ensures that all root nodes (if there were more than just the one "Sarah Johnson") are also linked for left/right navigation.

const data = [{
  name: "Sarah Johnson",
  position: "CEO",
  email: "[email protected]",
  id: "5555",
  children: [{
      name: "Michael Davis",
      position: "CFO",
      email: "[email protected]",
      id: "5556",
      children: [{
          name: "Sophia Adams",
          position: "Finance Manager",
          email: "[email protected]",
          id: "5557",
          children: [],
        },
        {
          name: "William Harris",
          position: "Financial Analyst",
          email: "[email protected]",
          id: "5558",
          children: [],
        },
        {
          name: "Oliver Turner",
          position: "Accounting Manager",
          email: "[email protected]",
          id: "5559",
          children: [],
        },
      ],
    },
    {
      name: "Robert Smith",
      position: "COO",
      email: "[email protected]",
      id: "5560",
      children: [{
          name: "Emily Wilson",
          position: "VP of Operations",
          email: "[email protected]",
          id: "5561",
          children: [],
        },
        {
          name: "Daniel Brown",
          position: "Director of Production",
          email: "[email protected]",
          id: "5562",
          children: [],
        },
        {
          name: "Sophie Turner",
          position: "Director of Logistics",
          email: "[email protected]",
          id: "5563",
          children: [],
        },
        {
          name: "Olivia Lee",
          position: "VP of HR",
          email: "[email protected]",
          id: "5564",
          children: [{
            name: "Ethan Miller",
            position: "HR Manager",
            email: "[email protected]",
            id: "5565",
            children: [],
          }, ],
        },
      ],
    },
  ],
}, ];

function link(node) {
  if (node.children[0]) node.down = node.children[0];
  for (var i = 0; i < node.children.length; i++) {
    node.children[i].up = node;
    if (i > 0) {
      node.children[i].left = node.children[i - 1];
      node.children[i - 1].right = node.children[i];
    }
    link(node.children[i]);
  }
}
link({
  children: data
});
var current = data[0];
currentNode.textContent = current.name;
document.addEventListener("keyup", function(event) {
  var node;
  switch (event.which) {
    case 40:
      node = current.down;
      break;
    case 38:
      node = current.up;
      break;
    case 37:
      node = current.left;
      break;
    case 39:
      node = current.right;
      break;
  }
  if (node?.name) {
    current = node;
    currentNode.textContent = current.name;
  }
});

<span id="currentNode"></span>

Collectives™ on Stack Overflow

How to write a function to navigate through a non-binary tree?

2 Answers 2

3 Comments

1 Comment

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

1 Comment

Related