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

danielblythe
November 4, 2023
77 views
0 votes
2 Answers

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,
}

I’m fairly lost on how to solve this problem.

Any help greatly appreciated.

Answers

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>

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>

Please signup or login to give your own answer.

Click here to cancel reply.

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

Answers