Hi Guys -
I was just playing around with HTML5 Canvas and thought it will be fun to create a binary tree implementation using JavaScript.
I tried this a few years ago with Java and applets. Well, yeah u guessed it, it was a PITA.
With JavaScript and Canvas, it was a smooth ride.
The code below is only for the purpose of demo. Some nodes might overlap if the tree has a lot
of nodes.
Tested on Google Chrome
1 - Create a file index.html and add the below code to it.
It contains an
a - Input box where the user will enter the number to be added
b - A button to add entered number
c - A canvas element
d - A script tag
2 - Next we will add a node object. Node, as the name suggests, represent a node in the tree
Add the below code in the script tag of the index.html
3 - Next we will add code to draw a line from parent to child. Add the below code to the script tag
4 - Next we add the core logic of a binary tree. To understand that logic, you should know how
a binary tree works. Add the blow code the script tag
5 - Now we need to create a binary tree object to which we can add node
Add the below code to the script tag
var btree = new BTree();
6 - Ok. We are almost done. We just need to wire the input box and add to tree button
Add the below code to the script tag
I was just playing around with HTML5 Canvas and thought it will be fun to create a binary tree implementation using JavaScript.
I tried this a few years ago with Java and applets. Well, yeah u guessed it, it was a PITA.
With JavaScript and Canvas, it was a smooth ride.
The code below is only for the purpose of demo. Some nodes might overlap if the tree has a lot
of nodes.
Tested on Google Chrome
1 - Create a file index.html and add the below code to it.
It contains an
a - Input box where the user will enter the number to be added
b - A button to add entered number
c - A canvas element
d - A script tag
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| <!DOCTYPE html> | |
| <html> | |
| <head> | |
| <style> | |
| .center {margin: auto; width: 50%;} | |
| <style> | |
| </head> | |
| <body> | |
| <div class='input-box'> | |
| <input id='tree-input' type='number' placeholder='Enter number'> | |
| <button id='add-to-tree' onclick="addToTree()">Add To Tree</button> | |
| </div> | |
| <div class="tree center"> | |
| <canvas id='my-canvas' width="400" height="400"> | |
| Your browser doesnot support canvas | |
| </canvas> | |
| </div> | |
| <script> | |
| </script> | |
| </body> | |
| </html> |
2 - Next we will add a node object. Node, as the name suggests, represent a node in the tree
Add the below code in the script tag of the index.html
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // Represents the node in the tree. Will be displayed as a small circle in the browser. | |
| // x, y --> x, y co-ordinates of the center of circle | |
| // r --> radius of the circle | |
| // ctx --> context of the canvas | |
| // data --> data to be displayed (Only number) | |
| var Node = function(x,y,r, ctx, data) { | |
| // left child of a node | |
| this.leftNode = null; | |
| // right child of a node | |
| this.rightNode = null; | |
| // draw function. Responsible for drawing the node | |
| this.draw = function() { | |
| ctx.beginPath(); | |
| ctx.arc(x, y, r, 0, 2*Math.PI); | |
| ctx.stroke(); | |
| ctx.closePath(); | |
| ctx.strokeText(data, x, y); | |
| }; | |
| // Simple getters | |
| this.getData = function() { return data; }; | |
| this.getX = function() { return x; }; | |
| this.getY = function() { return y; }; | |
| this.getRadius = function() { return r; }; | |
| // Returns coordinate for the left child | |
| // Go back 3 times radius in x axis and | |
| // go down 3 times radius in y axis | |
| this.leftCoordinate = function() { | |
| return {cx: (x - (3*r)), cy: (y + (3*r))} | |
| }; | |
| // Same concept as above but for right child | |
| this.rightCoordinate = function() { | |
| return {cx: (x + (3*r)), cy: (y+(3*r))} | |
| }; | |
| }; |
3 - Next we will add code to draw a line from parent to child. Add the below code to the script tag
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // Draws a line from one circle(node) to another circle (node) | |
| var Line = function() { | |
| // Takes | |
| // x,y - starting x,y coordinate | |
| // toX, toY - ending x,y coordinate | |
| this.draw = function(x, y, toX, toY, r, ctx) { | |
| var moveToX = x; | |
| var moveToY = y + r; | |
| var lineToX = toX; | |
| var lineToY = toY - r; | |
| ctx.beginPath(); | |
| ctx.moveTo(moveToX, moveToY); | |
| ctx.lineTo(lineToX, lineToY); | |
| ctx.stroke(); | |
| }; | |
| }; |
4 - Next we add the core logic of a binary tree. To understand that logic, you should know how
a binary tree works. Add the blow code the script tag
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // Represents the btree logic | |
| var BTree = function() { | |
| var c = document.getElementById('my-canvas'); | |
| var ctx = c.getContext('2d'); | |
| var line = new Line(); | |
| this.root = null; | |
| var self = this; | |
| // Getter for root | |
| this.getRoot = function() { return this.root; }; | |
| // Adds element to the tree | |
| this.add = function( data) { | |
| // If root exists, then recursively find the place to add the new node | |
| if(this.root) { | |
| this.recursiveAddNode(this.root, null, null, data); | |
| } else { | |
| // If not, the add the element as a root | |
| this.root = this.addAndDisplayNode(200, 20, 15, ctx, data); | |
| return; | |
| } | |
| }; | |
| // Recurively traverse the tree and find the place to add the node | |
| this.recursiveAddNode = function(node, prevNode, coordinateCallback, data) { | |
| if(!node) { | |
| // This is either node.leftCoordinate or node.rightCoordinate | |
| var xy = coordinateCallback(); | |
| var newNode = this.addAndDisplayNode(xy.cx, xy.cy, 15, ctx, data); | |
| line.draw(prevNode.getX(), prevNode.getY(), xy.cx, xy.cy, prevNode.getRadius(), ctx) | |
| return newNode; | |
| } | |
| else { | |
| if(data <= node.getData()) { | |
| node.left = this.recursiveAddNode(node.left, node, node.leftCoordinate, data); | |
| } | |
| else { | |
| node.right = this.recursiveAddNode(node.right, node, node.rightCoordinate, data); | |
| } | |
| return node; | |
| } | |
| }; | |
| // Adds the node to the tree and calls the draw function | |
| this.addAndDisplayNode = function(x, y, r, ctx, data) { | |
| var node = new Node(x, y, r, ctx, data); | |
| node.draw(); | |
| return node; | |
| }; | |
| }; |
5 - Now we need to create a binary tree object to which we can add node
Add the below code to the script tag
var btree = new BTree();
6 - Ok. We are almost done. We just need to wire the input box and add to tree button
Add the below code to the script tag
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| var addToTree = function() { | |
| input = document.getElementById('tree-input'); | |
| value = parseInt(input.value); | |
| if(value) | |
| btree.add(value); | |
| else | |
| alert("Wrong input"); | |
| }; |
