Javascript: Iterate through binary tree? [closed]

Question

How can I iterate through the following if I want to print all the pitches in order such that the left comes first and then right. For the following first piece of code; the answer should be a4, b4,c4,d4. How can I achieve this programmatically?

var melody2_mus = 
    { tag: 'seq',
      left: 
       { tag: 'seq',
         left: { tag: 'note', pitch: 'a4', dur: 250 },
         right: { tag: 'note', pitch: 'b4', dur: 250 } },
      right:
       { tag: 'seq',
         left: { tag: 'note', pitch: 'c4', dur: 500 },
         right: { tag: 'note', pitch: 'd4', dur: 500 } } }

Another Example:

 var melody2_mus = 
        { tag: 'seq',
          left: { tag: 'note', pitch: 'b4', dur: 250 } },
          right:
           { tag: 'seq',
             left: { tag: 'note', pitch: 'c4', dur: 500 },
             right: { tag: 'note', pitch: 'd4', dur: 500 } } }

should print b4, c4, d4

Thanks

Answer 1

A recursive function would be simplest:

function traverse(obj) {
    // always follow left branch first
    if (obj.left) {
        traverse(obj.left);
    }

    // do stuff for leaf nodes
    if (obj.pitch) {
        console.log(obj.pitch);
    }

    // then the right branch if it exists
    if (obj.right) {
        traverse(obj.right);
    }
}

See http://jsfiddle.net/alnitak/E2ZEB/

Or more generically:

function traverse(obj, func) {
    if (!obj) return;

    traverse(obj.left, func);
    func(obj);
    traverse(obj.right, func);
}

Answer 2

Here's a copy of Alnitak's answer, but abstracted with the visitor pattern.

function traverse(obj, cb) {
    cb(obj);
    if (obj.left) {
        traverse(obj.left, cb);
    }
    if (obj.right) {
        traverse(obj.right, cb);
    }
}

var melody2_mus = 
    { tag: 'seq',
      left: 
       { tag: 'seq',
         left: { tag: 'note', pitch: 'a4', dur: 250 },
         right: { tag: 'note', pitch: 'b4', dur: 250 } },
      right:
       { tag: 'seq',
         left: { tag: 'note', pitch: 'c4', dur: 500 },
         right: { tag: 'note', pitch: 'd4', dur: 500 } } }

traverse(melody2_mus, function(node) {
    if (node.pitch) {
        console.log(node.pitch);
    }
});

http://jsfiddle.net/E2ZEB/3/