Binary Tree Demo using JavaScript and Canvas.

Type numbers followed by commas and watch the tree getting made.

This video explains the process of using this demo.

Go ahead.

This is the old Binary Search Tree or BST implemented using JavaScript. A BST is a binary tree where every left node is less than or equal to the right nodes.
The first thing I implemented was a regex based system so that the user cannot type anything other than numbers (+ve or -ve) followed by commas.

This is the relevant code.




if (event.target.value.startsWith(","))
    event.target.value = event.target.value.replace(',', "");

var pattern = /, , / g;
event.target.value = event.target.value.replace(pattern, ",");
pattern = / -- / g;
event.target.value = event.target.value.replace(pattern, "-");
pattern = / [ ^ 0 - 9 +, +-] / g;
event.target.value = event.target.value.replace(pattern, "");

The first line checks for a starting comma and removes it, then the next pattern we look for is two continuous commas and we replace it with a single comma.

This being done, we then check for two consecutive -- signs and remove the extra one.

Finally, we check for numbers, - and , and allow nothing else.

The next part is breaking the input string into tokens. This has been done using the split function in JavaScript.




var a=event.target.value.split(",");

The next problem that we faced was the fact that JavaScript doesn't have pointers. I solved this problem by creating a one element object that I call a NullNode. It has one field called ptr. This enables me to pass a pointer. Take a look at the relevant code.




function vsjnullNode()
{
    return ({ptr:null});
}

The addNode to tree function is classic recursive stuff.


function vsjaddNode(root ,data)
{
  console.log(root);
i f(root.pt r= =null)
{
  var newnod e =vsjgetNode(data);

root.pt r =newnode;
console.log(root.ptr.data);
return;
}

i f(dat a< =root.ptr.data)
vsjaddNode(root.ptr.left ,data);
else
vsjaddNode(root.ptr.right ,data);
}
function vsjgetNode(data)
{
return({data :data ,left :vsjnullNode() ,right :vsjnullNode()});
}

Look at the way null node and the ptr field has been used.

The preorder, inorder and postorder are again classic recursive stuff.




function
vsjpreOrder(root)
{
if (root.ptr == null)
return;
var
data = root.ptr.data;
preoutput += vsjgetBox(data);
vsjpreOrder(root.ptr.left);

vsjpreOrder(root.ptr.right);

}
function
vsjpostOrder(root)
{
if (root.ptr == null)
    return;
var
data = root.ptr.data;

vsjpostOrder(root.ptr.left);

vsjpostOrder(root.ptr.right);
postoutput += vsjgetBox(data);

}
function
vsjinOrder(root)
{
if (root.ptr == null)
    return;
var
data = root.ptr.data;

vsjinOrder(root.ptr.left);
inoutput += vsjgetBox(data);
vsjinOrder(root.ptr.right);

}

Finally the code that actually draws the nodes on the canvas. This is done by dividing the horizontal screen into half parts at every stage. The vertical positioning is calculated using the height of the tree.

This is the code.





function
vsjdrawTreeBegin(root)
{

    var
canvas = document.getElementById("vsjtreeCanvas");
const
canvaswidth = canvas.width;
const
canvasheight = canvas.height;
var
ht = vsjtreeHeight(root);
var
ctx = canvas.getContext("2d");
ctx.clearRect(0, 0, canvaswidth, canvasheight);
console.log(canvaswidth + "," + canvasheight);
var
dx = canvaswidth / 2;
var
dy = canvasheight / ht;
vsjdrawTree(ctx, root, dx, 10, dx, dy, dx, 10);
}
function
vsjdrawTree(ctx, root, x, y, dx, dy, prevx, prevy)
{
if (root.ptr == null)
return;

vsjdrawCircle(ctx, x, y, root.ptr.data, prevx, prevy);
vsjdrawTree(ctx, root.ptr.left, x - dx / 2, y + dy, dx / 2, dy, x, y);
vsjdrawTree(ctx, root.ptr.right, x + dx / 2, y + dy, dx / 2, dy, x, y);
}
function
vsjdrawCircle(ctx, x, y, data, prevx, prevy)
{

ctx.beginPath();
ctx.moveTo(prevx, prevy);
ctx.lineTo(x, y);
ctx.stroke();
ctx.beginPath();
ctx.arc(x, y, 10, 0, 2 * Math.PI);

ctx.fillStyle = "wheat";

ctx.fill();
ctx.strokeStyle = "red";
ctx.stroke();
ctx.fillStyle = "blue";
ctx.strokeStyle = "blue";
ctx.font = "12px Verdana";
var
absdata = data;
if (absdata < 0)
    absdata = -absdata;
var
xdiff = 0;
if (absdata <= 9)
    xdiff = 3;
else
    if (absdata <= 99)
        xdiff = 8;
    else
    xdiff = 12;
ctx.strokeText(data, x - xdiff, y + 2);
}

The drawTreeBegin sets up the tree drawing configuration. The drawTree navigates recursvely while drawCircle does the actual drawing.

Here is the css style code





< style >
.vsjcard
{
    box - shadow: 0 4px 8px 0  # FFC604;
    transition: 0.3
s;
width: 5
px;
}

.vsjcard: hover
{
    box - shadow: 0 8px 16px 0  # FE413E;
}
.vsjinputTextArea
{
    font - weight: bolder;
width: 100 %;
box - sizing: border - box;
border - radius: 5
px;;
height: 50
px;
padding: 5
px;
text - align: center;

}
.vsjoutputdiv
{
    background - color: lightgrey;
width: 100 %;
box - sizing: border - box;
border - radius: 5
px;
padding: 5
px;
height: 200
px;
overflow: scroll;

}
.vsjcanvasclass
{
    background - color: white;
width: 100 %;
box - sizing: border - box;
border - radius: 5
px;
padding: 5
px;
height: 300
px;

}
.vsjroundeddiv
{
    valign: middle;
display: inline - block;
background - color: lightpink;
width: 50
px;
height: 50
px;
box - sizing: border - box;
border - radius: 60 %;
border - width: 5
px;
height: 30
px;
border - color: blue;
border - style: ridge;
text - align: center;

}

< / style >