Quick actions

cmd+k|ctrl+k

Navigation

Languages

Ordered Binary Tree - Sorting Traversal

Snippet info

Language

JavaScript

Visibility

public

Author

horngyih

Created

2017-09-20T01:14:48Z

Updated

2017-09-20T01:22:38Z

function OrderedBinaryTree(value){
    this.value = value || null;
    this.left = null;
    this.right = null;
}

OrderedBinaryTree.prototype.addRight = function(value){
    if( this.right ){
        this.right.addNode(value);
    } else {
        this.right = new OrderedBinaryTree(value);
    }
};

OrderedBinaryTree.prototype.addLeft = function(value){
    if( this.left ){
        this.left.addNode(value);
    } else {
        this.left = new OrderedBinaryTree(value);
    }
};

OrderedBinaryTree.prototype.addNode = function(value){
    if( this.value ){
        if( typeof value === "number" ){
            if( value > this.value ){
                this.addRight(value);
            } else {
                this.addLeft(value);
            }
        } else {
            this.addLeft(value);
        }
    } else {
        //Root Node
        if( this.isLeaf() ){
            this.addLeft(value);
        } else {
            if( this.left && this.right ){
                if( value > this.left.value ){
                    this.addRight(value);
                } else {
                    this.addLeft(value);
                }
            }
            else if( !this.right ){
                this.addRight(value);
            } else {
                this.addLeft(value);
            }
        }
    }
}

OrderedBinaryTree.prototype.isLeaf = function(){
    return !this.left && !this.right;
}

var root = new OrderedBinaryTree(null);

var sortTarget = [1, 9, 2, 50, 100, 34, 3 ];
for( var i in sortTarget ){
    root.addNode(sortTarget[i]);
}

function accumulator( prev, current ){
    prev = prev || [];
    if( current ){
        prev.push(current);
    }return prev;
}

function traverse( node, accumulator, prev, ascending ){
    ascending = ( typeof ascending !== "undefined" )? ascending : true;
    if( node ){
        if( node.isLeaf() ){
            return accumulator( prev, node.value );
        } else {
            var traversalPreference = [node.left, node.right];
            if(!ascending){
                traversalPreference = [node.right, node.left];
            }
            prev = traverse(traversalPreference[0],accumulator, prev, ascending );
            prev = accumulator(prev, node.value);
            prev = traverse(traversalPreference[1],accumulator, prev, ascending );

            return prev;
        }
    } else {
        return prev;
    }
}

console.log( "Target Array : ", sortTarget );
console.log( "Sorted Array (ascending) : ", traverse(root,accumulator) );
console.log( "Sorted Array (descending): ", traverse(root,accumulator, [], false) );
INFO