Need an algorithm to traverse a component tree

user_10255994 0
Viewed 42

I'm creating a React app that has a "SplitPane" component that is basically a div split horizontally or vertcally (The divider in the middle can be dragged for resizing):

 ____     _________     _________
|    |   |    |    |   |  |      |
|____|   |____|____|   |__|______|
|    |
|____|

These can be nested recursively, forming structure like the following:

 _____________
|     |___|   |
|     |___|___|
|_____|_____|_|
|       |     |
|_______|_____|
|_______|_____|

Or any other such arbitrary combination.

I would like the user to be able to reasonably switch between the cells with the arrow keys, but being that this is a component tree, it will look something like this in memory:

    H
   / \
  H   V
 / \ / \
*  * H  *
    / \
   *   H
      / \
     *   *

Where:

  • 'H' := horizontally split panes
  • 'V' := vertically split panes
  • '*' := leaf component

I would like to know if there is any sort of algorithm that can be used to easily traverse this tree to get the top, bottom, left, or right component which could be several branches away on the component tree.

splitpane reactjs traversal tree algorithm
1 Answers

Let's use three data structures: parent, first_child and level data structures.

The parent data structure, keeps track of the parent of the ith node.

The first_child data structure, keeps track of the first child of the ith node.

The level data structure, keeps track of the nodes in the ith level.

Consider the following tree :

     a   
    / \
   b   c

level[0] = {a}, level[1] = {b, c}

parent[b] = parent[c] = a

first_child[a] = b

When the up arrow is pressed, we go to the parent of the current node, when down arrow is pressed we go to the child, and when left and right arrow is pressed, we go to the left and right node in the particular level.

Note: Nodes in level[i] can be stored in a sorted order and use binary search to find the neighbors(left and right) efficiently. If we assign the key value of the react component with an increasing value each time, it'll be sorted by default.

user_98268520
Related