Plotting a binary tree in JavaScript
Tags: three, javascript, bfs, dfs
Published: 2020-09-24 01:23:54

A tree in computer science is a data structure that has a wide use in the field of computer science, it has a root, a sub-tree of children with a parent node, represented as a set of linked nodes. This data structure has extensive use cases, trees are the basis of other data structures such as Maps and Sets, in addition to a clear example of the use of trees are fast searches in databases and representing the HTML DOM hierarchy. There are different types of trees, however in this post we will implement and graph a binary tree using **Canvas** and **JavaScript**.

##What is a binary tree?
A binary tree is a data structure, it begins with a top node called **root** and **branches** with its descendants (sub-trees) until it finally ends at nodes called leaves. Each node can have a maximum of 2 children, **left and right**. In case that node does not have any reference, it means it does not have children, it is called **leaves or external node**.

##Implementing the binary tree data structure
In the previous blog you realized that a binary tree is a data structure, where each node has a value and pointers (links) to 2 children or descendants, below is the implementation of a node.
**Note:** It is assumed that the reader has knowledge of the tree data structure, so the explanation of its implementation will not be deepened.

```javascript
const LEFT = 0
const RIGHT = 1

class Node {
    constructor(value) {
        this.value = value
        this.children = []
        this.parent = null
        this.pos = { x: 0 , y: 0}
        this.r = 20
    }
    
    get left() { return this.children[LEFT] }
    
    set left(value) {
        value.parent = this
        this.children[LEFT] = value
    }
    
    get right() { return this.children[RIGHT]}

    set right(value) {
        value.parent = this
        this.children[RIGHT] = value
    }
    
    set position(position){ this.pos = position }
    
    get position(){ return this.pos }
    
    get radius() { return this.r }
}
```
Well, now that we have the node class, we are going to implement the Tree class, which allows inserting the child nodes, their value and position.

```javascript
class Tree{

    constructor(){
        this.root = null
        this.startPosition = {x: 800, y: 44}
        this.axisX = 350
        this.axisY = 80
    }
    
    getPosition({x , y}, isLeft = false){
        return { x: isLeft ? x - this.axisX + y : x + this.axisX - y, y: y + this.axisY }
    }
    
    add(value){
        const newNode = new Node(value)
        if(this.root == null){
            newNode.position = this.startPosition
            this.root = newNode
        } else {
            let node = this.root
                while(node){
                    if(node.value == value)
                        break
                    if(value > node.value){
                        if(node.right == null){
                            newNode.position = this.getPosition(node.position) //get current position of new node
                            node.right = newNode 
                            break
                         }
                         node = node.right
                     } else {
                         if(node.left == null){
                             newNode.position = this.getPosition(node.position,true) //get current position of new node
                             node.left = newNode
                             break
                         }
                         node = node.left
                     }
               }
        }
    }
    
    // bfs(){ ... } it will be implemented later
}
```
In the Tree class, 4 attributes are initialized in the constructor, which are:

1. **root** attribute refers to the root node of the tree.
2. **startPosition** is an attribute used to determine the position on the abscissa **axis or X** axis and its ordinate or **Y axis**, of the root node.
3. **axisX and axisY**, are numerical constants that allow the nodes to be moved graphically in the plane.
4. The **add method** of the Tree class allows inserting a new node in the tree, the position of the node is changed depending on whether it is a **left or right** node.
5. **getPosition** method receives the **X and Y position** as an argument, **isLeft flag** by default is false, this method allows to calculate the new position in plane of the new node. The constant **axisX** is added or subtracted from the X axis together with the position in Y, since in this axis less and less distance will move between nodes, while the depth of the tree is greater. On the other hand, the Y axis only adds the constant **axisY**, because the distance between the nodes on this axis will always be the same.

##Breadth First Search
To graph the binary tree in the plane, it is necessary to go through each node of the tree, for this there are 2 possibilities:
- The first is the [Depth First Search - DFS](https://en.wikipedia.org/wiki/Depth-first_search), which starts **from the root and expands each of the nodes to the end nodes or leaves**, for each of the branches, using a **stack** to temporarily store the nodes while traveling .
- The second option is the [Breadth First Search - BFS](https://en.wikipedia.org/wiki/Breadth-first_search), which starts **from the root and traverses each node through levels instead of branches**, using a **queue** to temporarily store nodes.

To graph the tree, I have decided to use the BFS since I prefer to graph the nodes by levels, it is true that when it is required to visit all the nodes of the tree it is better to use DFS since the search by width is efficient in finding the shortest path, however in this case tastes and preferences are far from being technical.

##It is time to graph the tree by implementing BFS
```javascript
var c = document.getElementById("myCanvas")
var ctx = c.getContext("2d")
...
bfs() {
    const queue = []
    const black = "#000"
    queue.push(this.root)
    
    while (queue.length !== 0) {
        const node = queue.shift()
        const {x, y} = node.position
        const color = "#" + ( (1<<24) * Math.random() | 0 ).toString(16)
        
        ctx.beginPath()
        ctx.strokeStyle = black
        ctx.fillStyle = color
        ctx.fill()
        ctx.stroke()
        ctx.strokeStyle = black
        ctx.strokeText(node.value, x, y)
        
        node.children.forEach(child => {
            const {x: x1, y: y1} = child.position
            ctx.beginPath();
            ctx.moveTo(x, y + child.radius)
            ctx.lineTo(x1, y1 - child.radius)
            ctx.stroke()
            queue.push(child)
        });
    }
}
```
The above algorithm is detailed below:

1. Create a **queue** variable, in javascript an array serves this purpose, **const queue = []**.
2. Insert **root** of the tree, **queue.push(this.root)**, into the queue.
3. As long as the queue has nodes, the following is done.
4. Remove the first item from the **queue** and return the item removed const **node = queue.shift()**.
5. Get the position of the deleted node **const {x, y} = node.position**, also the following line, calculates a color randomly.
6. Start a new route by emptying the list of sub-routes, since it is required to create a new route to plot the circumference, **ctx.beginPath()**.
7. Determine the color of the line, a black color in this case, **ctx.strokeStyle = black**, and also determine the fill color, **ctx.fillStyle = color**.
8. **Draw a circle**, you have to draw an arc of **360 degrees**, that is, **2π radians**, for this we use the method **ctx.arc(x, y, node.radius, 0, 2 * Math.PI)**, where X and Y is the center of the circumference, the next parameter is the **radius**, the **0** represents the starting angle and the last represents the final angle in radians.
9. Draw the previously defined line **ctx.stroke()**, and assign the black line again, **ctx.strokeStyle = black**.
10. Write the value of the node **ctx.strokeText(node.value, x, y)**, in the same position on the circumference.
11. For each child node that the parent node has **(node.children.forEach)** the following is done:
12. Gets the position of the child node **const {x: x1, y: y1} = child.position**.
13. Draw a line from the parent node **(ctx.moveTo (x, y + child.radius))**, to the child node **(ctx.lineTo (x1, y1 - child.radius))** joining the edges of each circumference.
14. Add the child node to the **queue.push(child)**.

Ready!. The method to graph the tree is implemented, it is time to put into operation the insert and graph methods of the tree class.

```javascript
const t = new Tree()
t.add(10)
t.add(5)
t.add(15)
t.add(3)
t.add(14)
t.add(16)
t.add(4)
t.add(6)
t.add(2)
t.bfs()
```
The result of the execution of the previous code will be the following.
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/utfgf922d6ftha6eenga.png)

This source code can be found on [GitHub](https://github.com/foqc/bfs-canvas-tree).

Was it useful? Show your support or share it!

**Thank you!!**