Pseudocodes

Binary Tree

/**
 * @class
 * @param {BinaryTreeNode} root
 */
function BinaryTree(root) {
    /**
     * @private
     * @type {BinaryTreeNode}
     */
    this.root = root; 
}

/**
 * @returns {BinaryTreeNode}
 */
BinaryTree.prototype.getRoot = function() {...}

/**
 * @param {BinaryTreeNode} root
 */
BinaryTree.prototype.setRoot = function(root) {...}

/**
 * Return number of nodes in tree.
 * @returns {Number}
 */
BinaryTree.prototype.getCount = function() {...}

/**
 * Build a tree from given array.
 * @param {Number[]} array
 */
BinaryTree.prototype.build = function(array) {...}

/**
 * Swap nodes and change all needed references. 
 * @param {BinaryTreeNode} node1
 * @param {BinaryTreeNode} node2
 */
BinaryTree.prototype.swapNodes = function(node1, node2) {...}

/**
 * Simulate an array implementation.
 * @param {Number} index
 * @returns {BinaryTreeNode}
 */
BinaryTree.prototype.getNode = function(index) {...}

/**
 * Simulate an array implementation.
 * @param {BinaryTreeNode} node
 * @returns {Number} Index of given node.
 */
BinaryTree.prototype.getIndex = function(node) {...}

Binary Tree Node

/**
 * @class
 * @param {Number|String} value The value of the node.
 */
BinaryTreeNode = function(value) {
    /**
     * @private
     * @type {Number|String}
     */     
    this.value = value;
    
    /**
     * @private
     * @type {BinaryTreeNode}
     */
    this.parent = null;
    
    /**
     * @private
     * @type {BinaryTreeNode}
     */
    this.left = null;
    
    /**
     * @private
     * @type {BinaryTreeNode}
     */
    this.right = null;
}
                                    
/**
 * @returns {Number}
 */
BinaryTreeNode.prototype.getValue = function() {...}

/**
 * @returns {Boolean}
 */
BinaryTreeNode.prototype.isRoot = function() {...}

/**
 * @returns {Boolean}
 */
BinaryTreeNode.prototype.isLeaf = function() {...}

/**
 * @returns {BinaryTreeNode}
 */
BinaryTreeNode.prototype.getParent = function() {...}

/**
 * Set left child and changes all needed references.
 * @param {BinaryTreeNode} left
 */
BinaryTreeNode.prototype.setLeft = function(left) {...}

/**
 * @returns {BinaryTreeNode}
 */
BinaryTreeNode.prototype.getLeft = function() {...}

/**
 * Set right child and changes all needed references.
 * @param {BinaryTreeNode} right
 */
BinaryTreeNode.prototype.setRight = function(right) {...}

/**
 * @returns {BinaryTreeNode}
 */
BinaryTreeNode.prototype.getRight = function() {...}

Heapify-down

Rearrange a heap to maintain the heap property downwards. If the node is not greater than or equal to its children, swap it with the greater child, then recursively heapify-down that child's subtree. Michael L. Littman

/**
 * @param {BinaryTree} tree
 * @param {BinaryTreeNode} node
 */
function heapifyDown(tree, node) {
    var left = node.getLeft();
    var right = node.getRight();
    var greaterChild;
    
    if(node.isLeaf()) { // no child, end
        return;
    }
    
    // get greater child
    if(left != null && right != null) { // both child, compare child
        if(left.getValue() >= right.getValue()) {
            greaterChild = left;    
        } else {
            greaterChild = right;
        }
    } else { // just left child
        greaterChild = left;
    }
    
    // swap and continue
    if(greaterChild.getValue() > node.getValue()) {
        tree.swapNodes(node, greater);
        heapifyDown(tree, node);
    }
}

Heapify-up

Rearrange a heap to maintain the heap property upwards. If the node is greater than its parent, swap these nodes, then recursively heapify-up the parent that changed (originally the given node). Michael L. Littman

  
/**
 * @param {BinaryTree} tree
 * @param {BinaryTreeNode} node
 */
function heapifyUp(tree, node) {    
    var parent = node.getParent();

    if(parent == null) {
        return;
    }

    // swap and continue
    if(parent.getValue() < node.getValue()) {
        tree.swapNodes(this.node, parent);
        heapifyUp(node);
    }
}

Random Binary Heap

Generate a new random binary heap. This is my own algorithm written for this application. This is not a general generator of random binary heaps.

/**
 * @param {BinaryTree} tree
 * @param {Number} min
 * @param {Number} max
 */
function randomHeap(tree, min, max) {

    var count = randomInt(1, Math.min(max - min + 1, 31));    
    var numbers = new Array(max - min + 1);
    var array = new Array();
    // generate array of random non identic numbers of scale
    for(var i = 0; i < count; i++) { 
        do{
            array[i] = randomInt(Math.ceil(min), Math.floor(max));
        } while (numbers[array[i] - min] == true);
        numbers[array[i] - min] = true;
    }

    buildHeap(tree, array);
}

Build Heap

Convert an array into a heap by executing heapify-down progressively closer to the root.Paul E. Black

/**
 * @param {BinaryTree} tree
 * @param {Number[]} array
 */
function buildHeap(tree, array) {

    tree.build(array);

    // use heapify-down from half of the tree to root
    for(var i = Math.floor(array.length/2) - 1; i >= 0; i--) {
        heapifyDown(tree, tree.getNode(i));
    }
}

Insert

The new node is initially appended to the end of the heap. The heap property is repaired by comparing the added node with its parent and swapping them if added node is grater than its parent. The comparison is repeated until the parent is larger than or equal to the percolating element.Victor Adamchik

/**
 * @param {BinaryTree} tree
 * @param {Number} value
 */
function insert(tree, value) {
    node = new BinaryTreeNode(value); 
    
    if(tree.getRoot() == null) { // empty tree
        tree.setRoot(node);
        return;
    }

    var index = tree.getCount();
    var parentIndex = Math.floor((index-1)/2);
    var parent = tree.getNode(parentIndex);
    if(index % 2 == 1) { // left
        parent.setLeft(node);
    } else { // right
        parent.setRight(node);
    }

    // maintain the heap property
    heapifyUp(node);
}

Delete

Remove the node and replace it with the last element of the heap and then restore the heap property. It is necessary to check for both up- and downshifts. For example when the "last" node takes up the vacant spot, it can be over- or underevaluated. It can't be both, for obvious reasons. Victor S.Adamchik Gaminic

/**
 * @param {BinaryTree} tree
 * @param {BinaryTreeNode} node
 */
function delete(tree, node) {
    if(tree.getRoot == node) {
        tree.setRoot(null);
        return;
    }

    // swap selected and last
    var last = tree.getNode(tree.getCount() - 1);
    if(node != last) {
        tree.swapNodes(node, last);
    }
    
    if(node.getParent().getLeft() == node) { // left
        node.getParent().setLeft(null);
    } else { // right
        node.getParent().setRight(null);
    }

    // heapify last, it is necessary to check for both ways, 
    // but only one heapify is done, the other end at the first comparison
    heapifyUp(tree, last);
    heapifyDown(tree, last);
}

Get Max

The heap property ensures the root is always maximum node.

/**
 * @param {BinaryTree} tree
 */
function getMax(tree) {
    return tree.getRoot();
}

Extract Max

Same as delete the root node. Root is always maximum node (the heap property).

/**
 * @param {BinaryTree} tree
 */
function extractMax(tree) {

    var max = tree.getRoot();    
    if(max != null) {
        delete(tree, max);
    }
    
    return max;
}

Heap Sort

A sort algorithm that repeatedly extracts the maximum from heap.Paul E. Black This implementation delete the whole tree and nodes are sorted in an array.

/*
 * @param {BinaryTree} tree
 */
function heapSort(tree) {    
    var array = new Array();

    while(tree.getRoot() != null) {
        array.push(extractMax(tree));
    }

    array.reverse();
    return array;
}

Random Binary Search Tree

Generate a new random binary search tree. This is my own algorithm written for this application. This is not a general generator of random binary trees.

/**
 * @param {BinaryTree} tree
 * @param {Number} min
 * @param {Number} max
 */
function randomBSTree(tree, min, max) {

        var epsilon = (max - min)/4;

        tree.setRoot(new BinaryTreeNode(randomInt(Math.floor(min+epsilon), Math.ceil(max-epsilon))));
    
        randomBSTreeRec(tree.getRoot(), 1, min, max);
    }  
}   

/**
 * @param {BinaryTreeNode} node
 * @param {Number} level
 * @param {Number} min
 * @param {Number} max
 */
function randomBSTreeRec(node, level, min, max) {

    if(min >= node.getValue() - 1 || node.getValue() + 1 >= max) { // safety
        return;
    }
    
    var chance;
    if(level <= 3 && Math.random() < 0.33) { // make both child - generated tree is fuller
        chance = 1.0;
    } else {
        switch(level) {
            case 1: chance = 0.95; break;
            case 2: chance = 0.5; break; 
            case 3: chance = 0.3; break;
            case 4: chance = 0.1; break;            
            default: chance = 0.0; break; // no node at higher levels
        }
    }
    
    var epsilon = (max - min)/4;
    
    // left child
    if(chance > Math.random()) {
        node.setLeft(new BinaryTreeNode(randomInt(Math.floor(min + epsilon), Math.ceil(node.getValue() - epsilon))));
        if(node.getLeft().getValue() == min) {
            min += 1;
        }
        randomBSTreeRec(node.getLeft(), level + 1, min, node.getValue() - 1);
    }
    
    // right child
    if(chance > Math.random()) {
        node.setRight(new BinaryTreeNode(randomInt(Math.floor(node.getValue() + epsilon), Math.ceil(max - epsilon))));
        if(node.getRight().getValue() == max) {
            max -= 1;
        }
        randomBSTreeRec(node.getRight(), level + 1, node.getValue() + 1, max);
    }
}

Insert

Insert algorithm traverses the tree, choosing appropriate way to go by comparing value of each visited node with the new value, following the binary search tree property. Following this simple rule, the algorithm reaches a node, which has not a subtree to go. Appended new node here.algolist.net

/**
 * @param {BinaryTree} tree
 * @param {Number} value
 */
function insert(tree, value) {
    var newNode = new BinaryTreeNode(value); 

    if(tree.getRoot() == null) { // empty tree
        tree.setRoot(node);
        return;
    }

    var node = tree.getRoot();
    while(true) {
        if(newNode.getValue() >= node.getValue()) { // right subtree
            node = node.getRight();
            if(node == null) {
                node.setRight(newNode); // insert
                break; // end
            }
        } else { // left subtree
            node = node.getLeft();
            if(node == null) { 
                node.setLeft(newNode); // insert
                break; end
            }
        }
    }    
}

Find

Search algorithm traverses the tree, choosing appropriate way to go by comparing value of each visited node with the searched value, following the binary search tree property. Algorithm stops if a node with necessary value is found or the algorithm has no way to go.algolist.net

/**
 * @param {BinaryTree} tree
 * @param {Number} value
 * @return {BinaryTreeNode}
 */
function find(tree, value) {
    
    var node = tree.getRoot();
    while(true) {
        if(node.getValue() == node.getValue()) { // found
            return node; 
        }

        if(node.getValue() > node.getValue()) { // right
            if(node.getRight() == null) { // not found
                break;
            } else { // next comparison
                node = node.getRight();
            }
        } else { // left
            if(node.getLeft() == null) { // not found
                break;
            } else { // next comparison
                node = node.getLeft();
            }
        }
    }   

    return null; // not found
}

Delete

There are three cases:

• Node to be removed has no children: Algorithm sets corresponding link of the parent to NULL.
• Node to be removed has one child: In this case, node is cut from the tree and algorithm links single child (with it's subtree) directly to the parent of the removed node.
• Node to be removed has two children: In this case node to be removed is swapped with its successor (in that case it is minimum from right subtree). Then it is deleted as node with no or one child because minimum of subtree cannot have tho children.algolist.net

/**
 * @param {BinaryTree} tree
 * @param {BinaryTreeNode} node
 */
function delete(tree, node) {

    if(node.getLeft() != null  && node.getRight() != null) { // both children
        var successor = getSuccessor(node);
        tree.swapNodes(node, successor);
    } // continue normally - delete node
    
    // now just one or no child
    if(node.getLeft() != null) { // just left child

        var leftSubtreeRoot = node.getLeft();
        if(node.isRoot()) { // is root, no parent, set tree root
            node.setLeft(null);
            tree.setRoot(leftSubtreeRoot);
        } else {
            if(node.getParent().getLeft() == node) { // left child
                node.getParent().setLeft(leftSubtreeRoot);
            } else { // right child
                node.getParent().setRight(leftSubtreeRoot); 
            }
        }
    }
    else if(node.getRight() != null) { // just right child
        
        var rightSubtreeRoot = node.getRight();
        if(node.isRoot()) { // is root, no parent, set tree root
            node.setRight(null);
            tree.setRoot(rightSubtreeRoot);
        } else {
            if(node.getParent().getLeft() == node) { // left child
                node.getParent().setLeft(rightSubtreeRoot);
            } else { // right child
                node.getParent().setRight(rightSubtreeRoot); 
            }
        }
    }
    else { // no child
        if(node.isRoot()) { // is root, no parent, set tree root
            tree.setRoot(null);
        } else {
            if(node.getParent().getLeft() === node) { // left child
                node.getParent().setLeft(null);
            } else { // right child
                node.getParent().setRight(null);
            }
        }
    }
}

Get Max

The binary search tree property ensures the maximum node is always the most right one.

/**
 * @param {BinaryTreeNode} root Root of (sub)tree.
 */
function getMax(root) {
    
    var max = root;
    while(max.getRight() != null) {
        max = max.getRight();
    }

    return max;
}

Get Min

The binary search tree property ensures the minimum node is always the most left one.

/**
 * @param {BinaryTreeNode} root Root of (sub)tree.
 */
function getMin(root) {

    var min = root;
    while(min.getLeft() != null) {
        min = min.getLeft();
    }

    return min;
}

Get Predecessor

See get successor algorithm. Get predecessor is similar, but look for maximum of left subtree or ancestor from right.

/**
 * @param {BinaryTreeNode} node
 */
function getPredecessorAlg(node) {

    if(node.getLeft() != null) { // has left subtree
        return getMax(node.getLeft()); // return max of left subtree of given node
    }
    else { // no left subtree, try find predecessor in ancestors
        
        var child = node;
        var parent = node.getParent();
        while(true) {
            if(parent == null) { // no parent, no predecessor
                return null; // no predecessor found
            }

            if(parent.getRight() == child) { // arrived from right
                return parent; // predecessor found
            }

            // next loop
            child = parent;
            parent = parent.getParent();
        }
    }
}

Get Successor

• 1. The node has a right subtree.
  The next larger node must be in the right subtree. Since all nodes in a right subtree are larger than or equal to the given node, the successor must be the smallest of all those nodes (minimum of right subtree).

• 2. The node does not have a right subtree.
  In this case we will have to look up the tree since that's the only place we might find the next larger node. There is no point looking at the left subtree as all nodes in the left subtree are guaranteed to be smaller than the given node.
  When we look up from the given node, there can be two cases. First, the current node is the left child of its parent. In this case the parent is the successor node. This is because the parent always comes next in in-order traversal if you are done with left subtree (rooted at the current node). Second, the current node is the right child of the parent. This is an interesting case. In this case, as you keep going up the ancestor chain you encounter smaller values if you are going up but larger values if you are going right. The successor node will be the first node up the ancestor chain that you encounter on the right chain.Golam Kawsar

/**
 * @param {BinaryTreeNode} node
 */
function getSuccessorAlg(node) {

    if(node.getRight() != null) { // has left subtree
        return getMin(node.getRight()); // return min of right subtree of given node
    }
    else { // no right subtree, try find successor in ancestors
        
        var child = node;
        var parent = node.getParent();
        while(true) {
            if(parent == null) { // no parent, no successor
                return null; // no successor found
            }

            if(parent.getLeft() == child) { // arrived from left
                return parent; // successor found
            }

            // next loop
            child = parent;
            parent = parent.getParent();
        }
    }
}

To Pre-order Array

To traverse a tree data structure is to process every node exactly once. However you may "pass through" a node many times. For pre-order walk process node itself, recursively traverse its left subtree, recursively traverse its right subtree.Robert Holte

/**
 * @param {BinaryTree} tree
 */
function toPreorderArray(tree) {
    var array = new Array();

    var node = tree.getRoot();
    if(node == null) {
        return array; // empty tree
    } 

    array.push(node);
    toPreorderArrayRec(node.getLeft(), array);
    toPreorderArrayRec(node.getRight(), array);

    return array;
}   

/**
 * @param {BinaryTreeNode} node
 * @param {BinaryTreeNode[]} array
 */
function toPreorderArrayRec(node, array) {
    if(node == null) {
        return;
    }

    array.push(node);
    toPreorderArrayRec(node.getLeft(), array);
    toPreorderArrayRec(node.getRight(), array);
}

To In-order (Sorted) Array

To traverse a tree data structure is to process every node exactly once. However you may "pass through" a node many times. For in-order walk recursively traverse node's left subtree, process node itself, recursively traverse node's right subtree.Robert Holte

/**
 * @param {BinaryTree} tree
 */
function toInorderArray(tree) {
    var array = new Array();

    var node = tree.getRoot();
    if(node == null) {
        return array; // empty tree
    } 

    toInorderArrayRec(node.getLeft(), array);
    array.push(node);
    toInorderArrayRec(node.getRight(), array);

    return array;
}   

/**
 * @param {BinaryTreeNode} node
 * @param {BinaryTreeNode[]} array
 */
function toInorderArrayRec(node, array) {
    if(node == null) {
        return;
    }

    toInorderArrayRec(node.getLeft(), array);
    array.push(node);
    toInorderArrayRec(node.getRight(), array);
}

To Post-order Array

To traverse a tree data structure is to process every node exactly once. However you may "pass through" a node many times. For post-order walk recursively traverse node's left subtree, traverse node's right subtree, process node itself.Robert Holte

/**
 * @param {BinaryTree} tree
 */
function toPostorderArray(tree) {
    var array = new Array();

    var node = tree.getRoot();
    if(node == null) {
        return array; // empty tree
    } 

    toPostorderArrayRec(node.getLeft(), array);
    toPostorderArrayRec(node.getRight(), array);
    array.push(node);

    return array;
}   

/**
 * @param {BinaryTreeNode} node
 * @param {BinaryTreeNode[]} array
 */
function toPostorderArrayRec(node, array) {
    if(node == null) {
        return;
    }

    toPostorderArrayRec(node.getLeft(), array);
    toPostorderArrayRec(node.getRight(), array);
    array.push(node);
}