About graph traversal and treeview-component for representing tree data with ReactJS
In frontend development, sometimes there are tasks of representing a tree-like data structure. For example, we can cite the tasks of implementing a pipeline with branching according to the states of the execution steps, or the structure of the chains of the questionnaire with the options for proposing the next question or the final decision based on previous answers. In UI, such elements can (and often should) be interactive and resilient to large amounts of data.
Live Demo: https://treeview-component.vercel.app
Since such a structure is an undirected graph, and the task of finding elements in a tree inevitably arises, search algorithms are needed. Two search algorithms can come to the rescue here: Depth-first and Breadth-first.
A bit of theory
The four traversals that will be discussed are called pre-order traversal, in-order traversal, post-order traversal, and breadth-first search. Let’s start by giving them more precise definitions, and then look at a few examples where these models can be useful.
Pre-order traversal
- Check if the current node is empty or null
- Show the data field of the root (or the current node)
- Traverse the left subtree recursively by calling the pre-order traversal function
- Traverse the right subtree recursively by calling the pre-order traversal function
In-order traversal
- Check if the current node is empty or null
- Traverse the left subtree recursively by calling the in-order traversal function
- Show the data field of the root (or the current node)
- Traverse the right subtree recursively by calling the in-order traversal function
Post-order traversal
- Check if the current node is empty or null
- Traverse the left subtree recursively by calling the post-order traversal function
- Traverse the right subtree recursively by calling the post-order traversal function
- Show the data field of the root (or the current node)
Breadth-first
Trees can also be traversed in level order, where we visit each node in the level before moving on to the next level.
All of the above implementations require a stack proportional to the height of the tree, which is the call stack for the recursive implementation and the parent stack for the iterative one. In a poorly balanced tree, this stack can be significant. In an iterative implementation, we can get rid of the stack by storing its parent for each node or by flashing the tree.
Traversal is usually performed for trees with a finite number of nodes (and therefore with a finite depth and a finite branching ratio), but it can also be performed for infinite trees. This traversal is of interest, in particular, in functional programming (for lazy computation), since infinite data structures can often be easily defined and manipulated, although they cannot be (strictly) computed as it would take infinite time. Some finite trees are too large to represent explicitly, so it makes sense to treat them as infinite.
The main requirement for a traversal is to visit all nodes. For infinite trees, simple algorithms cannot do this. For example, if you have a binary tree of infinite depth, depth-first search will move along one side (usually the left side) of the tree, never visiting the other vertices, and moreover, a centered or backward traversal will never visit any node, since it will never reaches the leaf. In contrast, breadth-first traversal (level-wise) traverses an infinite-depth binary tree without issue, and moreover, traverses any tree with a limited branching ratio.
Let’s practice
Now let’s move on to the React implementation of the component for representing the tree and the traversal function of such a structure, which is needed to display connections between nodes and insert children to the parent.
Here I show examples with class based code style, but you of course can reproduce all of them with functional code style.
The example above creates a tree class constructor, which receives data from the original structure through props and reflects this structure to a public variable of the class. Also, from the outside, the component will wait for the component to be displayed at the top of the graph (the review will display the links on its own). The result of the function breaking the structure into nesting layers is written to the local state of the component. It will be an array with arrays of vertices on each layer (in this example, the branching direction of the graph is horizontal). A listing of the createColumnsData function is shown below:
This function traverses the tree depth-first using the pre-order traversal method. This creates a stack of parents. Here you can clearly see that the stack allows you to define a parent for a vertex, in the case when the vertex does not contain such a link.
Now that the graph is decomposed layers and there is a component for displaying vertices, it remains only to decide how to display the connections between the vertices on the page. The problem can be stated as follows: it is necessary to show the connection between the vertices of the graph Bezier curves originating from the center of the right side of the parent vertex and coming to the left side of the child vertex. To do this, you need to calculate the height of the vertices and the distance in height between the exit and entry points. The implementation might look like this:
Next, you need to update the view as a result of the first initialization and changes in the structure during user interaction. To do this, we use the lifecycle functions of the React component:
And finally, let’s describe the render itself:
For more convenient work with the graph, the Panzoom component has been added to the page, which allows you to scale the graph and move it inside the container. The result of using the component can be a graph, as in the figure below:
This example, enables the display of empty vertices with the ability to add new ones to the tree:
You can learn more about the component at npm https://www.npmjs.com/package/treeview-component
