javascriptalgorithmsearchbinary-treebinary-search-tree

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


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.

enter image description here

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: "sarah.johnson@aaaaaaa.com.au",
    id: "5555",
    children: [
      {
        name: "Michael Davis",
        position: "CFO",
        email: "michael.davis@aaaaaaa.com.au",
        id: "5556",
        children: [
          {
            name: "Sophia Adams",
            position: "Finance Manager",
            email: "sophia.adams@aaaaaaa.com.au",
            id: "5557",
            children: [],
          },
          {
            name: "William Harris",
            position: "Financial Analyst",
            email: "william.harris@aaaaaaa.com.au",
            id: "5558",
            children: [],
          },
          {
            name: "Oliver Turner",
            position: "Accounting Manager",
            email: "oliver.turner@aaaaaaa.com.au",
            id: "5559",
            children: [],
          },
        ],
      },
      {
        name: "Robert Smith",
        position: "COO",
        email: "robert.smith@aaaaaaa.com.au",
        id: "5560",
        children: [
          {
            name: "Emily Wilson",
            position: "VP of Operations",
            email: "emily.wilson@aaaaaaa.com.au",
            id: "5561",
            children: [],
          },
          {
            name: "Daniel Brown",
            position: "Director of Production",
            email: "daniel.brown@aaaaaaa.com.au",
            id: "5562",
            children: [],
          },
          {
            name: "Sophie Turner",
            position: "Director of Logistics",
            email: "sophie.turner@aaaaaaa.com.au",
            id: "5563",
            children: [],
          },
          {
            name: "Olivia Lee",
            position: "VP of HR",
            email: "olivia.lee@aaaaaaa.com.au",
            id: "5564",
            children: [
              {
                name: "Ethan Miller",
                position: "HR Manager",
                email: "ethan.miller@aaaaaaa.com.au",
                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?


Solution

  • 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: "sarah.johnson@aaaaaaa.com.au",id: "5555",children: [{name: "Michael Davis",position: "CFO",email: "michael.davis@aaaaaaa.com.au",id: "5556",children: [{name: "Sophia Adams",position: "Finance Manager",email: "sophia.adams@aaaaaaa.com.au",id: "5557",children: [],},{name: "William Harris",position: "Financial Analyst",email: "william.harris@aaaaaaa.com.au",id: "5558",children: [],},{name: "Oliver Turner",position: "Accounting Manager",email: "oliver.turner@aaaaaaa.com.au",id: "5559",children: [],},],},{name: "Robert Smith",position: "COO",email: "robert.smith@aaaaaaa.com.au",id: "5560",children: [{name: "Emily Wilson",position: "VP of Operations",email: "emily.wilson@aaaaaaa.com.au",id: "5561",children: [],},{name: "Daniel Brown",position: "Director of Production",email: "daniel.brown@aaaaaaa.com.au",id: "5562",children: [],},{name: "Sophie Turner",position: "Director of Logistics",email: "sophie.turner@aaaaaaa.com.au",id: "5563",children: [],},{name: "Olivia Lee",position: "VP of HR",email: "olivia.lee@aaaaaaa.com.au",id: "5564",children: [{name: "Ethan Miller",position: "HR Manager",email: "ethan.miller@aaaaaaa.com.au",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>