Code Samurai

Question: Given a node, write an algorithm to determine if that node is in binary tree?

This is one of the basic algorithms about binary tree that you should know how to implement. It can help aid in designing other algorithms for solving more complicated problems such as finding the Lowest Common Ancestor of two nodes in a binary tree.

Moreover, job interviewers may ask you to implement it or use it to solve some other problems. Thus, spending a few minutes to understand the algorithm is definitely worth it.

Here is a the recursive / easiest algorithm to answer the question:

public boolean isNodeInTree(Node node, Node root)
{
 if (node == null || root == null)
  return false;
 if (root.data == node.data)
  return true;
 
 return isNodeInTree(node, root.left) || isNodeInTree(node, root.right);
}

In short, we just look at every node under the binary tree. And we do it recursively.

If the node we're looking at is null or if the node we're looking for is null then the node we're looking for is not in the tree.

Next, if the current node has the same data as the node we're searching for then return true because we've found what we need.

Otherwise, we'll continue to do the same for both the left and right child of the current node. And return true if we find the node we need in either left or right child. In case both left and right child don't contain the node we need then it is not in the tree.

Welcome back to another edition of "Drawing Basic Shapes with HTML5 Canvas." Here are the links to the first three parts: part 1, part 2 and part 3.

This post will cover the last part of the series. Specifically, we'll draw a circle using HTML5 Canvas. If you find the explanation difficult to understand, please review the previous parts of the tutorial. I covered a lot of basic information in those parts.

Alright, here we go!

Circle:

As usual, please check out the code first and try to see if you can understand it. Then, you can read the explanation.

<!DOCTYPE HTML>
  <html>
    <body>
      <canvas id="myCanvas" width="200" height="100" style="border:1px solid #c3c3c3;">
        Your browser does not support the canvas element.
      </canvas>
      <script type="text/javascript">
        var c=document.getElementById("myCanvas");
        var cxt=c.getContext("2d");
        cxt.fillStyle="#FF0000";
        cxt.beginPath();
        cxt.arc(70,18,15,0,Math.PI*2,true);
        cxt.closePath();
        cxt.fill();
      </script>
    </body>
  </html>

<canvas>: as usual, we define a canvas with specified dimension and id. We also make the canvas border visible for easy drawing.

<script>: we first get a reference to our canvas and then get the its 2D drawing context. If you don't know what a context is, please review the second part of the tutorial.

fillStyle(): use red color to fill our circle.
beginPath(): this method creates a new path for custom drawings. What is a path? It is a collection of different sketches and strokes. A shape is considered a path because a shape is made up of many different strokes (lines, arcs, ...). Each path has its own properties such as stroke color and fill color.
arc(): draw an arc or a circle. The full method signature is arc( center_x, center_y, radius, startAngle, endAngle, antiClockwise).

center_x and center_y: the coordinates of the center of the circle or arc.

radius: radius of the circle / arc.

startAngle and endAngle: start and end point of the circle / arc in radian. If you forgot your trigonometry, use this JavaScript formula to convert degree to radian (Math.Pi / 180) * degree. Since we draw circle, we need to start our angle at 0 and end our angle at 360 degree or PI * 2.

antiClockwise: a boolean that is true to draw the circle / arc anti-clockwise and false to do the opposite.

closePath(): end the path after we has done our drawing. When drawing many different shapes on the same canvas, we must call beginPath() and closePath() for each shape.

fill(): fill our circle with specified color (red).

Here is a picture. Hope it helps to clear up any confusion:

Well, that concludes our tutorial. If you have any question / suggestion please leave it in the comment below.

I'm preparing for more advanced tutorial on HTML5 Canvas! So check back for more goodies later :)

Code Samurai

Search This Blog

Monday, January 10, 2011

Searching for a node in a binary tree

Monday, January 3, 2011

Drawing Basic Shapes with HTML5 Canvas (last Part)