# Pseudocodes

A little of a theory. There are definitions of used data structures (Binary Tree, Binary Heap, Priority Queue, Binary Search Tree) and simplified actually used codes of algorithms.
Binary Tree Visualiser is written in JavaScript, so these codes are also written in JavaScript syntax. Codes are simplified to show the main functionality. Extreme cases (given empty tree, null node, etc.) are usually not solved.
Make sure you know the basics about JavaScript. It is a scripting language. It is object oriented, dynamic typed, prototype based and has first-class functions. In JavaScript object are passed by references, but primitive types by values. There are no classes. Functions are used as objects constructors, and prototyping is used for inheritance.developer.mozilla.org

## Binary Tree

A binary tree is an data structure with one root node (the ancestor of all nodes). Each node has a value and at most two child nodes, usually called left child and right child. Each node (except for root) has one parent. Root node has no parent. Node with no children is called leaf.
The formal recursive definition is: a binary tree is either empty (represented by a null), or is made of a single node, where the left and right references (recursive definition ahead) each point to a binary tree.Nick Parlante

### 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() {...}```

## Binary Heap + Priority Queue

A binary heap is a binary tree. In addition it meets these two condition:

• The tree is a complete binary tree: a binary tree in which every level, except possibly the deepest, is completely filled, and all nodes must be as far left as possible.
• The heap property: each node is lower than or equal to its parent.Chris L. Kuszmaul

A priority queue is an abstract data type to efficiently support finding the item with the highest priority (highest value) across a series of operations (nodes). The basic operations are: insert, get maximum and extract maximum.Paul E. Black In Binary Tree Visualiser there is priority queue implemented as binary heap with these functions.

### 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;

}```

## Binary Search Tree

A binary search tree is a type of binary tree where the nodes are arranged in order: for each node, all nodes in its left subtree are less than the node, and all the nodes in its right subtree are greater than or equal to the node. Recursively, each of the subtrees must also obey the binary search tree constraint.Nick Parlante

### 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

break;

} else { // next comparison

node = node.getRight();

}

} else { // left

break;

} else { // next comparison

node = node.getLeft();

}

}

}

}```

### 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

There are two options:
• 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);

}```