The generational divide in Japanese culture/cinema is a fertile trope for many storytellers. Stories of youth rebelling against adults and the established order, and even posing a very serious and devastating threat, provide the context for films like Akira (1986); the failure of adults to pass the values and responsibility for society is also a central theme to Akira Kurosawa’s King Lear adaptation Ran (1985). There may be no greater film exploring this divide and the inability of the previous generations to bridge that gap than Kinji Fukusaku’s Battle Royale (2000).

The setting is established using austere titles at the beginning of the film that announce a terrifying situation in Japan where the nation has collapsed and there is a 15% unemployment rate. The students are boycotting school, millions are out of work and fear of the youth lead the government to pass the Millenium Educational Reform Act, aka the “Battle Royale” Act. The games are covered by the media, and are seemingly intended to control the youth though the students have no conception of the law when they are selected to be the game’s players.

Released as a novel in 1999 and adapted for film in 2000, Battle Royale’s influences can be seen in the concept for the Hunger Games trilogy as well as the filmmaking of Quentin Tarantino, who reveres the film and cast one of its actors as Gogo Yubara in Kill Bill. Nearly prevented from being released in Japan, the extreme plot has its foundations in the experiences of the director Kinji Fukusaku during World War II. In an interview with The Guardian, director Kinji Fukusaku’s recounts his wartime experiences when he was the same age as the high school students in the film:

I was working in a weapons factory that was a regular target for enemy bombing. During the raids, even though we were friends working together, the only thing we would be thinking of was self-preservation. We would try to get behind each other or beneath dead bodies to avoid the bombs. When the raid was over, we didn't really blame each other, but it made me understand about the limits of friendship. I also had to clean up all the dead bodies after the bombings. I'm sure those experiences have influenced the way I look at violence.”

Battle Royale is permeated with ire and indignation, both of elders for their children and from the children for their elders. The main character, Shuya Nanahara, is raised by his father after his mother leaves the family until his father’s suicide on the first day of seventh grade. As an orphan that has had his trust betrayed by his parents, his only relationships are with his classmates, though he is haunted by memories of his father’s suicide. Another student’s mother prostitutes her child to a predator while hoping that her daughter is not weak and unable to manage her responsibilities like her.

The only adult in the film is played by the famous Japanese actor “Beat” Takeshi Kitano, who plays a former teacher named “Kitano”. Seen at the beginning of the film being stabbed by one student in the leg, Kitano returns as the students learn of their selection in the annual Battle Royale and relishes the terrible fortune of his former students. He mocks them, and advises them not to become “an adult” like their current teacher, who is shot dead for opposing their selection for the Battle Royale.

In this scene, we first see the characters interact with an adult, and the dramatic corpse-strewn gulf that separates them. Kitano feigns disappointment in the students, but tells them “the country is now good for nothing,” and kills two students for their insubordination while telling them about the rules of the game. This scene is critical for displaying the transition of the established adult authority (teachers, military) to a culture of fear from a shame society. It does not matter that the kids don’t fear the Battle Royale Act or its consequences, and their ignorance is not shameful; society now fears the youth and is using them as pawns to fight a murderous game in an attempt to exert control. Fear and danger form the foundation of the game, and if the students don’t obey and play the game, they will be killed by the government anyway.

The progression from disregarded teacher/authority figure Kitano, whose class the students mockingly won’t attend and is stabbed by one orphaned student, to feared despot demonstrates this degeneration. The threat of Kitano is established by his casual murder of two students and regular updates of the death toll, which is cheerfully broadcast across the island site as he mocking reads off the list of “goners”. While initially the teacher was dejected by his class’s lack of respect for school and him, he has become an enthusiastic participant of the game and even brings gifts to the students he likes, who will later aid him in his suicide and put him out of the misery that his adult life has become.

Another student, Shinji Mimura, builds a bomb and hacks the military’s network in an effort to rebel against the military and government while devoting no effort to playing the game. Mimura’s uncle, a soldier of fortune, taught him bomb-making and provided other military instruction and is seen as a positive force in young Mimura’s life. Similarly, one of the transfer students absurdly credits his surgeon/fisherman/polymath father for having given him every skill needed to protect himself or others, demonstrating that adults do have valuable information to give to the younger generation, but are incapable of providing them with a functional society or performing their parental roles.

The film’s absurdity and dark humor wonderfully underpin the ridiculous plot and make it more palatable. The concept for the film has inspired so many other stories, though it is the central Japanese themes, dark humor and ridiculous teenage melodrama that distinguish it from the flavorless repeats that followed. It is a great choice for kickstarting this series of 21st century films, both for its release date in 2000 and for its depiction of a new world, born from the calamity of the previous one and desperate to place itself apart from it.

No one moves to LA for love. Romance seekers with a poetic bent flock to cities like Paris or New York in search of magic, but LA is more sleight-of-hand, more glitter than gold. It thrives on the promise of being discovered and becoming the person you dream yourself to be, and the beauty of the sunny California landscapes. LA also maintains a reputation as a smoggy, arid sprawl with a hollow center, making it an easy target for cynics. This contrast earned LA its not-so-pejorative nickname La La Land, and it’s this conflicted earnestness that is the center of the film.

La La Land opens to a crane shot of a traffic jam on a freeway listening to isolated music in their cars, some singing, some idly resting their heads against their hands as they wait. The camera stops on a woman in a colorful dress as she sings, leaves the car and initiates a technically stunning set piece that involves the entire overpass in a choreographed number filmed with a combination of cranes and a steadicam. The scene includes bands waiting in the backs of trucks to perform their part as soon as the door is opened. The scene is edited well enough that it gives the illusion that it was filmed in one take, Once the song ends, the dancers get back in their cars and continue honking against the frustration of being stuck in a traffic jam.

The intro song perfectly sets up the film, as it depicts a surreal scene that is so precise that the audience is taken in and suspends disbelief immediately. The lyrics in the song, ‘Another Day of Sun’, suggest irony but still cheer for the people who want to be a part of the artifice: “The Technicolor world made out of music and machine/ It called me to be on that screen/ And live inside its sheen.” It’s difficult to describe just how entertaining this scene is, and how effectively it prepares the viewer for the rest of the film. Readers who haven’t seen the movie are correct if they think I was hoodwinked.

We meet the main characters when the number is finished, with Emma Stone giving Ryan Gosling the finger and he honks his horn while shaking his head disapprovingly. The audience and the characters themselves know they are going to be together as they sing about how odd it is that they continue to meet while moving from disdain to mild chemistry.

The leads are charming and funny, which helps because they carry the whole movie. They aren’t the young, naive characters that Chazelle originally cast Emma Watson and Miles Teller for, and it is hard to imagine this movie with those actors. Emma Stone continues to bring terrific performances to most of her movies, and Ryan Gosling can get a lot of acting mileage from the expressions around his eyes. Damien Chazelle does a pretty good job as director, I guess.

Just look at that face.

But let’s get back to the heart of La La Land. The characters endure trials, tribulations and whatever coffee people in southern California drink. They have dreams as artists and they don’t want to compromise their integrity. This might sound trite, but the characters are convincing and it’s really difficult not to get caught up in the romance and their aspirations. Emma Stone even sings a song titled ‘The Fools Who Dream’ at a pivotal moment in the film, and it is very affecting. Some people might find it too sentimental, but Stone deserves a lot of credit for saving it from becoming too cloying.

La La Land is full of nostalgia for older Hollywood movies, and uses old tropes to keep the viewer entertained. It has a lot of love for the artists who travel to LA or anywhere else to realize their dreams, and although the odds of becoming a star are extreme, someone has to perform for the audience. There are a lot of criticisms to make of La La Land, like what happened to Rosemarie DeWitt’s character, and why is she in the movie at all? Or why does the progression of the story sacrifice all ensemble dance pieces later in the film? But the film is about emotion, and you get it from little things like the sound of a car horn or big things like bittersweet moments that the audience knows are impossible but get anyway, just to have it taken away when the story returns to reality.

The quadtree data structure is a tree structure that retains data in an efficient way and optimizes lookups for values that are stored according to a specific configuration. This configuration is often spacial and is well suited to GPS coordinate systems because the individual x-y coordinates are placed in the tree based on their location. It is also used frequently in two-dimensional collision detection, because the constant lookups are only performed in specific portions of the quadtree to reduce lookup time.

The quadtree's strength in storing and retrieving data lies in its ability to subdivide itself into quadrants continually, depending on a threshold of coordinates contained within a quadrant. For example, if one section of a map has many coordinate points while another has few, the quadtree will optimize for storing the data such that the lookup on a loosely populated quadrant will not suffer from the traversal and lookup of the other branches of the tree structure. This allows fast lookup and offers 0(n log n) time complexity, greatly optimizing the process for real-time updating of dynamic data.

My team used a quadtree to store all of the GPS coordinate points for our app, Ripple, because the data was updated every one minute and needed constant accessing. For this reason we decided to store the data in memory, and clear it out every few minutes if an update was not received for a given coordinate/user id pair. The coordinates would also need to be accessed and compared against other coordinate points to find the distance between them, as our app filtered certain actions on a given coordinate if it was “outside” of the boundaries of a circle.

For the fast lookups and efficient storage, the most important operation our quadtree would need to perform was subdivision of itself, creating new quadtree nodes each composed of 1/4th the area of the parent quadtree node. It would need to do this when certain criteria was met, such as exceeding the maximum number of coordinate points for a given quadrant. This check was performed whenever a coordinate point was inserted into the quadtree, and the code to subdivide involved calculation the total coverage of each quadrant:

Quadtree.prototype.subDivide = function() {  
  var root = this;
  var depth = this.depth + 1;
  var width = this.boundaries.width / 2;
  var height = this.boundaries.height / 2;
  var x = this.boundaries.x;
  var y = this.boundaries.y;

  // top left quadrant
  this.quadrants[0] = new Quadtree({
    x: x,
    y: y + height,
    width: width,
    height: height
  }, this.maxChildren, root, depth);

with the quadrant setting process repeated three more times for each quadrant. Additionally, we coded an unfolding function that will collapse the quadrants into the parent node if the coordinates are too few to justify the subdivisions, and redistribute the coordinates within the parent node:

Quadtree.prototype.unfold = function(quad) {

  // check if root 
  if (quad.children.length && !quad.quadrants.length) {
    quad.root.unfold(quad.root);
  }

  var count = 0;

  quad.quadrants.forEach(function(quadrant) {
    count += quadrant.children.length;
  });

  if (count < quad.maxChildren / 2) {
    var nodes = quad.quadrants.reduce(function(acc, quadrant) {
      if (quadrant.children.length) {
        acc = acc.concat(quadrant.children);
      }
      return acc;
    }, []);

    quad.quadrants = [];

    nodes.forEach(function(node) {
      quad.put(node);
    });
  }
 };

Our app, Ripple, also allowed users to broadcast images to nearby users, depending on the GPS coordinates. These images would not be sent to users outside of a specific vicinity, which required that the system lookup a coordinate to find nearby nodes without needing check distant node. To increase lookup times and eliminate unnecessary comparisons, our quadtree only traverses through quadrants within the radius of the broadcast event, and performs this check/recurses only when it is required:

Quadtree.prototype.get = function(item, callback) {  
  if (this.quadrants.length) {

    if (this.checkRange(item)) {
      var index = this.findIndex(item);
      return this.quadrants[index].get(item);
    }

    else if (callback) {
      callback(this.quadrants[index].get(item));
    }

    else {
      return this;
    }
  }

  else if (!this.quadrants.length && this.children.length) {

    if (callback) {
      callback(this);
    }

    else {
      return this;
    }
  }

  else {
    console.log('returning root');
    return this.root || this;
  }
};

The checkDistance function will simply add the supplied vector length to the coordinate in 4 directions to find whether the radius is “in-bounds” or “out-of-bounds” of the quadrant before recursing further. If the distance is not “in-bounds” of the subquadrant, our function will not recurse further, but will simply traverse through all the quadrants and subquadrants of the node on top of the call stack, and perform the check on all of those coordinates.

Our distance checking function used the Haversine formula to calculate the distance between any two points, accounting for the great-circle arc of the earth's surface:

calculateDist: function(item1, nodes) {

// var R is the mean radius of the earth in kilometers
    var R = 6371;
    var lat1 = +item1.x;
    var lon1 = +item1.y;
    var lat2, lon2, dlat, dlon;
    var result = [];

    nodes.forEach(function(item2) {
      lat2 = +item2.x;
      lon2 = +item2.y;
      dLat = (lat2 - lat1).toRad();
      dLon = (lon2 - lon1).toRad();
      var a = Math.sin(dLat/2) * Math.sin(dLat/2) +
              Math.cos(lat1.toRad()) * Math.cos(lat2.toRad()) *
              Math.sin(dLon/2) * Math.sin(dLon/2);
      var c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a));
      var d = R * c;
      d = d * 0.621371;

      if (d < item1.radius) {
        result.push({userId: item2.userId, y: item2.y, x: item2.x});
      }
    });
    return result;
  }

Using this code, we can only find the coordinates that match our distance, and we will only look up the nodes that we absolutely have to. If we only include the amount of users currently using the app, the lookups are not terrible. However, once we begin testing the quadtree with one million, two million or 10 million users, we begin to see the value of the optimization, and can rest more easily knowing that our system will be able to handle millions of users demanding instant feedback and response from Ripple.

The Amazon Products Advertising API allows you to retrieve Amazon product information, including customer/seller reviews, images, prices, promotions and most of the information on Amazon's site pertaining to the products. Visitors to your site wishing to make a purchase can be directed to a virtual shopping cart that Amazon hosts on their servers and buy their products directly through Amazon. Additionally, you can earn revenue if you are a member of the Amazon Associates program and refer users to purchase products from Amazon through your site. Any way to generate passive income is a Good Thing.

I recently used this API to add a feature to an existing web app during the Legacy project at Hack Reactor. The app acted as a buyers club and utilized Venmo to facilitate the transfer of money between users when a certain threshold was met. I added the Amazon Products Advertising API to directly allow users to browse Amazon's products and buy the goods when the requisite funding was raised. You can add the Product Advertising API to your site by following these instructions:

The first thing you need to do is setup an Amazon Advertising Products API developer account by visiting this link, which can be linked with your Amazon retail account, if you are an Amazon customer.

You must also visit this Amazon AWS site and navigate to the Identity and Access Management (IAM) console to get your Amazon Access Key ID and Secret Access Key, which will be used to sign all of your requests. More on this later.

The API itself proved to be much more difficult than I anticipated. The latest version of the API was released in 2013, and the documentation was last updated June 24, 2014. All requests are made and returned in XML, and the process to create a proper request takes 10 steps. The request must be signed using a timestamp and the commas and colons must be URL encoded. Most importantly, a keyed-hash message authentication code (HMAC) must be created using the SHA256 hashing algorithm to sign the request before you can direct users to buy products from Amazon.

Fortunately for NPM users, there is a small library that will perform all of these functions for you, the Amazon Product Advertising API Client for Node (https://www.npmjs.com/package/apac) will parse our requests into XML, create the Request Signatures required by the Products API and parse the results to JSON for you. Although I spent too much unnecessary time researching the best method to accomplish all of this natively, you can reap the benefits as soon as you type npm install apac. And after you set up your AWS account, of course.

You only need to specify the type of action you want to take ('ItemSearch' or 'CreateCart', for instance) and an object that will contain the query parameters to be sent. The result will be parsed into JSON as an array of arrays, with each object property another array, leading to code that looks like this:

var item = results[index].ItemAttributes[0];  
var itemPrice = item.ListPrice ? item.ListPrice[0].FormattedPrice[0] :"N/A";  
$scope.imageURL = results[index].ImageSets[0].ImageSet[0].MediumImage[0].URL[0]

$scope.searchResults.push({
    'title': item.Title[0],
    'price': itemPrice,
    'img': results[index].ImageSets[0].ImageSet[0].MediumImage[0].URL[0],
    'description': results[i].EditorialReviews[0].EditorialReview[0].Content[0],
    'asin': results[index].ASIN[0]
});

I am currently preparing a pull request that converts the returned values to a more easily accessed object, though the repo has not been updated much since 2010.

With the popularity of Ionic and the hybridization of web/phone apps, any web developer with even a passing interest in producing phone apps should prepare their environment to do so. In this post, I will walk through the steps of creating an Ionic Android app, using Linux.

Ionic is an open-source, hybrid mobile/web platform for developing mobile apps using HTML5, CSS, and Javascript components; specifically AngularJS. As of this writing, it is among the top 40 most popular open source projects on Github with over 16,000 stars. Ionic's developer Drifty also claims an estimated 500,000 apps have been built with the development kit, and it only reached alpha status in November 2013.

Ionic can be used to build Android and iOS apps, and I recently developed an app for Android. After spending a considerable amount of time preparing my Ubuntu 14.10 machine for this purpose, I've compiled varied and scattered resources on the topic.

To develop for iOS using Ionic/Cordova, you will need to take additional steps if you are not running OS X, including using OpenSSL to generate a private key for use in signing your app. But I will focus on Android-specific development here.

The first step is to test whether java is installed, so type

java -version

If you see a java version number, you can skip ahead to the installation of the android development kit.

Otherwise, type

sudo apt-get update && sudo apt-get install default-jdk

to install OpenJDK. OpenJDK version 1.7.0.79 is functionally the same as Oracle's distribution, which Oracle engineers claim is based on the open-source version.

Alternately, you can download the JDK directly from Oracle here. Select your OS architecture and flavor (x86 or x64, Windows or OS X, etc.), accept the Oracle Binary Code License Agreement, and download the archive.

Once Java is installed, you will need to install the Android development kit as well. Navigate here and click the 'Download - Installing the SDK' link on the left sidebar. Unzip the file by using the command

tar zxvf android-sdk_r24.1.2-linux.tgz

Now, we have to make sure that we have defined the paths properly. If the archive was unzipped in your home directory, open the ~/.bashrc file and add these lines:

export PATH=${PATH}:~/android-sdk-linux/tools export PATH=${PATH}:~/android-sdk-linux/platform-tools

We are almost finished, but we need to install Apache Cordova and Ionic on Ubuntu. We can use Node Package Manager for this, and if this is not installed, open the terminal and enter:

sudo apt-get install nodejs

and

sudo npm install npm -g

to get the latest version.

Now, to install Cordova and Ionic, enter:

sudo npm install -g cordova

and

sudo npm install -g ionic

using the -g flag to install globally on your machine.

You can now create a new template and begin working. You can select a starter project at http://ionicframework.com/getting-started/, such as the side menu template, using

ionic start myApp sidemenu

to create a new project that you can use to learn Ionic. Remember to consult AngularJS documentation for information on developing for Ionic.

Good luck!

Mike Bostock's Data Driven Documents library uniquely allows for DOM elements to represent data interactively, and provides visually interesting transitions to attract and direct the viewer's attention. The New York Times, which employs Mr. Bostock as a graphical designer, makes excellent use of the library to convey information to the online reader that the information alone cannot. But why is D3 special, when similar functions can be performed by existing libraries like jQuery?

D3's tools can cover some of the same ground as jQuery, but it is capable of so much more when dynamically updating a web page with new data, and displaying that change. While jQuery can be used to add and manipulate DOM elements, D3 supplies better methods to use the DOM to project data.

Let's look at some code to compare. This jQuery code will produce a simple bar chart using jQuery, courtesy of Derek Mack (source here: http://provide.smashingmagazine.com/graphtutfiles/ex_03.html)

The jQuery method requires that we create containers for each graph element, and for the data that we will use in the graph. We also need to determine the scale for the graph, and set that before we even begin handling the data in visual form.

var figureContainer = $('<div id="figure"></div>');
var graphContainer = $('<div class="graph"></div>');
var barContainer = $('<div class="bars"></div>');
var data = $(data);
var container = $(container);

chartData = tableData.chartData();      
chartYMax = tableData.chartYMax();
columnGroups = tableData.columnGroups();

    chartYMax: function() {
        var chartData = this.chartData();
        var chartYMax = Math.ceil(Math.max.apply(Math, chartData) / 1000) * 1000;
        return chartYMax;
        },

    columnGroups: function() {
        var columnGroups = [];
        var columns = data.find('tbody tr:eq(0) td').length;
        for (var i = 0; i < columns; i++) {
            columnGroups[i] = [];
            data.find('tbody tr').each(function() {
                columnGroups[i].push($(this).find('td').eq(i).text());
            });
        }
        return columnGroups;
    }

    var tableData = {
    chartData: function() {
        var chartData = [];
        data.find('tbody td').each(function() {
            chartData.push($(this).text());
        });
        return chartData;
    },

    chartYMax: function() {
        var chartData = this.chartData();
        var chartYMax = Math.ceil(Math.max.apply(Math, chartData) / 1000) * 1000;
        return chartYMax;
    },

    yLegend: function() {
        var chartYMax = this.chartYMax();
        var yLegend = [];
        var yAxisMarkings = 5;                      
        for (var i = 0; i < yAxisMarkings; i++) {
            yLegend.unshift(((chartYMax * i) / (yAxisMarkings - 1)) / 1000);
        }
        return yLegend;
    },

    columnGroups: function() {
        var columnGroups = [];
        var columns = data.find('tbody tr:eq(0) td').length;
        for (var i = 0; i < columns; i++) {
            columnGroups[i] = [];
            data.find('tbody tr').each(function() {
                columnGroups[i].push($(this).find('td').eq(i).text());
            });
        }
        return columnGroups;
    }

    var xLegend = tableData.xLegend();      
    var xAxisList   = $('<ul class="x-axis"></ul>');
    $.each(xLegend, function(i) {           
        var listItem = $('<li><span>' + this + '</span></li>')
        .appendTo(xAxisList);
    });
       xAxisList.appendTo(graphContainer);

    var yLegend = tableData.yLegend();
    var yAxisList   = $('<ul class="y-axis"></ul>');
    $.each(yLegend, function(i) {           
        var listItem = $('<li><span>' + this + '</span></li>')
        .appendTo(yAxisList);
    });
    yAxisList.appendTo(graphContainer);     

    barContainer.appendTo(graphContainer);      

    graphContainer.appendTo(figureContainer);

    figureContainer.appendTo(container);

    function displayGraph(bars, i) {        
        if (i < bars.length) {
            $(bars[i].bar).animate({
            height: bars[i].height
             }, 800);
         barTimer = setTimeout(function() {
            i++;                
            displayGraph(bars, i);
        }, 100);
    }

    $.each(columnGroups, function(i) {
        var barGroup = $('<div class="bar-group"></div>');
        for (var j = 0, k = columnGroups[i].length; j < k; j++) {
            var barObj = {};
            barObj.label = this[j];
            barObj.height = Math.floor(barObj.label / chartYMax * 100) + '%';
            barObj.bar = $('<div class="bar fig' + j + '"><span>' + barObj.label +                    '</span></div>')
            .appendTo(barGroup);
            bars.push(barObj);
        }
        barGroup.appendTo(barContainer);            
    });

function resetGraph() {
    $.each(bars, function(i) {
    $(bars[i].bar).stop().css('height', 0);
    });`

Now, here is some D3 code for creating a bar chart:

<svg class="chart" data-bar-chart data-data="23,43,10,13,10,20,30,23,43,10,13,10,20,30" data-bar-width="15"></svg>
<svg class="chart" data-bar-chart data-data="19,65,23,31,32,44,5,32,23,23,54,65" data-bar-width="15"></svg>
<svg class="chart" data-bar-chart data-data="34,43,65,21,5,43,43,32,32,12,31,32,12,32,23,12" data-bar-width="15"></svg>

<script src="http://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<script src="http://d3js.org/d3.v3.min.js"></script>
<script>

$('[data-bar-chart]').each(function (i, svg) {
    var $svg = $(svg);
    var data = $svg.data('data').split(',').map(function (datum) {
    return parseFloat(datum);
});

var barWidth = parseFloat($svg.data('bar-width')) || 15;
var barSpace = parseFloat($svg.data('bar-space')) || 0.5;
var chartHeight = $svg.outerHeight();

var y = d3.scale.linear()
.domain([0, d3.max(data)])
.range([0, chartHeight]);

d3.select(svg)
    .selectAll("rect")
    .data(data)
    .enter().append("rect")
    .attr("class", "bar")
    .attr("width", barWidth)
    .attr("x", function (d, i) { return barWidth*i + barSpace*i; })
    .attr("y", chartHeight)
    .attr("height", 0)
    .transition()
    .delay(function (d, i) { return i*100; })
    .attr("y", function (d, i) { return chartHeight-y(d); })
    .attr("height", function (d) { return y(d); });
    });
</script>

I have omitted the HTML and CSS for these code snippets, but they are similar enough that their absence doesn't make a significant difference. While D3 cannot match jQuery for versatility and browser compatibility, it never was intended to, and is unparalleled in its ability to represent data within a web page.

A binary search tree provides many advantages to other data storage methods, offering O(log n) time complexity by organizing the data in an ordered pattern. Depending on a value comparison between the parent node and the child node, the data structure determines the placement of the node on the tree after initially determining whether the value being inserted is less than or greater than the root node. When searching for a node's value, half of the data structure is ignored while this value comparison continues down the tree and repeats at every node.

The structure also provides numerous methods to traverse the tree in a specific order. The traversal pattern familiar to web developers is the depth first search method, which traverses down a branch until there are no more leaves on that branch. This pattern can be represented simply in code using Douglas Crockford's WalkTheDom function, found in the excellent book Javascript: The Good Parts.

var walkDOM = function (node,func) {
  func(node);                 
  node = node.firstChild;
  while(node) {
    walkDOM(node,func);
    node = node.nextSibling;
  }
};

However, the Breadth First Search pattern also offers a way to move through the Binary Seach Tree, or any tree, depending on your intent. This method separates the tree structure into levels, with each child of a node representing a new level:

While the Walk the Dom method has many applications for web developers, the breadth first search pattern is less intuitive to programmers. But it does have some use, such as accessing nodes along the same plane, or rank, like military or organizational hierarchies. Additionally, if you know that the node you are looking for is relatively close to the beginning node, time spent moving deeper along a branch is wasted when the solution is several layers up.

Depth First Search traversals can commonly be performed with the use of a recursive function call; if there is a subordinate element, execute the function on that element, until the most distant element from the start point is acted on. Once the end of the branch has been reached, other branches are accessed.

The Breadth First Search traversal is similar, in that the same approach can be taken. We want to do something to the tree structure as long as our base case isn't met. We can utilize a common queue (First In, First Out) structure to traverse the tree.

function breadthFirstSearch(callback) {
  var nodeList = [this],
   node = nodeList[0];
   while (node) {
     if (node.left.value !== undefined) nodeList.unshift(node.left);
     if (node.right.value !== undefined) nodeList.unshift(node.right);
     callback(nodeList.pop());
     node = nodeList[nodeList.length - 1];
    }
}

The code for a traditional tree is less elegant but accomplishes the same thing. The array will never contain more than the parent node and its children, which allows traversal of the data structure without creating an array with too many objects.

function breadthFirstSearch(callback) {
  var nodeList = [this],
  node = nodeList[0];
  while (node) {
    if (node.children.length > 0) {
      for (var i = 0; i < node.children.length; i++) {
        nodeList.unshift(node.children[i])
      }
    }
  callback(nodeList.pop());
  node = nodeList[nodeList.length - 1];
}