Lists utils

list-methods.js

function nodeList(head, tail) {
    this.head = head;
    this.tail = tail;
}

nodeList.fromArray = function(array) {
  // method to convert a JS array to an algebraic list.
  let list = new nodeList(array[0], null);
  for (let i = 1, max = array.length; i < max; i++) {
    let node = list;
    while (node.tail) { node = node.tail; }
    node.tail = new nodeList(array[i], null);
  }
	return list;
};

function toArray(list) {
  // method to convert an algebraic list to array.
  if (list) {
    const hasTail = list.tail;
    return [list.head].concat(hasTail? toArray(hasTail) : []);
  }
  return [];
}

function filter(list, predicate){
  // returns a new list containing only elements that satisfy the predicate function.
  let filteredList = null;
  let lastNode = null;
  while (list) {
    if (predicate(list.head)) {
      if (!filteredList) {
        filteredList = new nodeList(list.head, null);
        lastNode = filteredList;
      } else {
        lastNode.tail = new nodeList(list.head, null);
        lastNode = lastNode.tail;
      }
    }
    list = list.tail;
  }
  return filteredList;
}

function map(list, mapper) {
  // returns a new list containing all elements resulting from applying the mapper functiont to them.
  let mappedList = null;
  let lastNode = null;
  while (list) {
    if (!mappedList) {
      mappedList = new nodeList(mapper(list.head), null);
      lastNode = mappedList;
    } else {
      lastNode.tail = new nodeList(mapper(list.head), null);
      lastNode = lastNode.tail;
    }
    list = list.tail;
  }
  return mappedList;
}

nodeList.prototype.toArray = function() { return toArray(this); };
nodeList.prototype.filter = function(predicate) { return filter(this, predicate); };
nodeList.prototype.map = function(mapper) { return map(this, mapper); };

Lists-Utils.markdown

Lists utils

list-methods.js

Class nodeList has a static method fromArray(array) that generates an algebraic list from provided array.

Class nodeList instance has methods:

• toArray() that generates an array from an algebraic list
• filter(predicate) that returns a new algebraic list where list nodes' head values satisfy provided predicate function
• map(mapper) that returns a new algebraic list with mapper function applied to each list nodes' head

tree-branches-max-sum.js

Function treeBranchMaxSum(root) traverses provided binary tree root and returns maximal branch sum from root to leaf.

sum-tree-values.js

Function sumTreeValues(root) traverses provided binary tree root and returns sum of all tree nodes' value properties.

tree-height.js

Function treeHeight(root) traverses provided binary tree root and returns length of the longest branch not counting root as a unit of length (e.g. if branch is 0124 and 0 is root, then branche's length is 3).

tree-printer.js

Function printTree(root) traverses a provided tree (not necessarily binary) and returns the tree represented as a multiline string where each row is a depth level of the tree. Tree node's value property is either a string or a number. Tree node's children property is an array containing all of the node's children.

Example tree node : Node { value: X, children: [] }

Example input:

• 2
  • 7
    • 2
    • 6
      • 5
      • 11
  • 5
    • 9
      • 4

Example output:

2\n7 5\n2 6 9\n5 11 4

2
7 5
2 6 9
5 11 4

Scripts by V.

License.

sum-tree-values.js

function sumTreeValues(root) {
  if (!root) { return 0; }
  let branches = [[]];
  let firstNode = root;
  let node = root;
  while (node) {
    let curNode = node;
    // determine direction
    let direction = (node.left) ? 'left' : (node.right) ? 'right' : 'restart';
    if (direction === 'left') {
      if (node.left.visited && node.right) { direction = (!node.right.visited) ? 'right' : 'break'; }
      if (node.left.visited && !node.right) { direction = 'break'; }
    } else
    if (direction === 'right') {
      if (node.right.visited && node.left) { direction = (!node.left.visited) ? 'left' : 'break'; }
      if (node.right.visited && !node.left) { direction = 'break'; }
    }
    // mark node
    if (node.right && node.left && !node.right.visited && !node.left.visited) {
      // false if node is a fork
      node.visited = false;
    } else {
      node.visited = true;
      // look forward for forks
      let next = (node.right) ? node.right : (node.left) ? node.left : null;
      while (next) {
        if (next.right && next.left && !next.right.visited && !next.left.visited) {
          node.visited = false;
        }
        next = (next.right) ? next.right : (next.left) ? next.left : null;
      }
    }
    // resolve direction and store value
    if (direction === 'break') {
      branches.pop();
      break;
    }
    branches[branches.length - 1].push(node.value); // store value
    node.value = 0; // drop value so that it does not affect result
    if (direction === 'left') { node = node.left; }
    if (direction === 'right') { node = node.right; }
    if (direction === 'restart') {
      if (node === root && !node.left && !node.right) {
        break;
      }
      node = firstNode;
      branches.push([]);
    }
  }
  //console.log(branches);
  branches = branches.reduce((a, b) => a.concat(b), []);
  return branches.reduce((a, b) => a + b, 0);
}

// TEST
/*
*      4
*    /   \
*  -30    11
*  / \    / \
* 7  60  7   3
*/
const root = new TreeNode(4, new TreeNode(-30, new TreeNode(7), new TreeNode(60)), new TreeNode(11, new TreeNode(7), new TreeNode(3)));
sumTreeValues(root); // 62

tree-branches-max-sum.js

function TreeNode(value, left, right) {
  this.value = value;
  this.left = left;
  this.right = right;
};

function treeBranchMaxSum(root) {
  //console.log('root:', root);
  if (!root) { return 0; }
  let branches = [[]];
  let firstNode = root;
  let node = root;
  while (node) {
    //console.log('#~ node >', node);
    let curNode = node;
    // determine direction
    let direction = (node.left) ? 'left' : (node.right) ? 'right' : 'restart';
    if (direction === 'left') {
      if (node.left.visited && node.right) { direction = (!node.right.visited) ? 'right' : 'break'; }
      if (node.left.visited && !node.right) { direction = 'break'; }
    } else
    if (direction === 'right') {
      if (node.right.visited && node.left) { direction = (!node.left.visited) ? 'left' : 'break'; }
      if (node.right.visited && !node.left) { direction = 'break'; }
    }
    // mark node
    if (node.right && node.left && !node.right.visited && !node.left.visited) {
      // false if node is a fork
      node.visited = false;
    } else {
      node.visited = true;
      // look forward for forks
      let next = (node.right) ? node.right : (node.left) ? node.left : null;
      while (next) {
        if (next.right && next.left && !next.right.visited && !next.left.visited) {
          node.visited = false;
        }
        next = (next.right) ? next.right : (next.left) ? next.left : null;
      }
    }
    // resolve direction and store value
    if (direction === 'break') {
      branches.pop();
      break;
    }
    branches[branches.length - 1].push(node.value); // store value
    if (direction === 'left') { node = node.left; }
    if (direction === 'right') { node = node.right; }
    if (direction === 'restart') {
      if (node === root && !node.left && !node.right) {
        break;
      }
      node = firstNode;
      branches.push([]);
      //console.log('===');
    }
  }
  //console.log('branches:', branches);
  branches.forEach((item, index) => {
    branches[index] = item.reduce((a, b) => a + b, 0);
  });
  return Math.max(...branches);
}

// TEST
/*
*      4
*    /   \
*  -30    11
*  / \    / \
* 7  60  7   3
*/
const root = new TreeNode(4, new TreeNode(-30, new TreeNode(7), new TreeNode(60)), new TreeNode(11, new TreeNode(7), new TreeNode(3)));
treeBranchMaxSum(root); // 34

tree-height.js

function treeHeight(root) {
  //console.log(root);
  if (!root) { return 0; }
  let branches = [[]];
  let firstNode = root;
  let node = root;
  while (node) {
    let curNode = node;
    // determine direction
    let direction = (node.left) ? 'left' : (node.right) ? 'right' : 'restart';
    if (direction === 'left') {
      if (node.left.visited && node.right) { direction = (!node.right.visited) ? 'right' : 'break'; }
      if (node.left.visited && !node.right) { direction = 'break'; }
    } else
    if (direction === 'right') {
      if (node.right.visited && node.left) { direction = (!node.left.visited) ? 'left' : 'break'; }
      if (node.right.visited && !node.left) { direction = 'break'; }
    }
    // mark node
    if (node.right && node.left && !node.right.visited && !node.left.visited) {
      // false if node is a fork
      node.visited = false;
    } else {
      node.visited = true;
      // look forward for forks
      let next = (node.right) ? node.right : (node.left) ? node.left : null;
      while (next) {
        if (next.right && next.left && !next.right.visited && !next.left.visited) {
          node.visited = false;
        }
        next = (next.right) ? next.right : (next.left) ? next.left : null;
      }
    }
    // resolve direction and store data
    if (direction === 'break') {
      branches.pop();
      break;
    }
    branches[branches.length - 1].push(node.data); // store data
    if (direction === 'left') { node = node.left; }
    if (direction === 'right') { node = node.right; }
    if (direction === 'restart') {
      if (node === root && !node.left && !node.right) {
        break;
      }
      node = firstNode;
      branches.push([]);
    }
  }
  //console.log('branches:', branches);
  return branches.reduce((a, b) => (a.length < b.length) ? b : a, []).length - 1;
}

// TEST
function Node (data) {
  this.data = data;
  this.left = null;
  this.right = null;
}
const root = new Node(3);
let nextNode = root;
nextNode.left = new Node(2);
nextNode = nextNode.left;
nextNode.left = new Node(1);
nextNode = root;
nextNode.right = new Node(5);
nextNode = nextNode.right;
nextNode.left = new Node(4);
nextNode.right = new Node(6);
nextNode = nextNode.right;
nextNode.right = new Node(7);

/**
* Node {
* data: 3,
* left: Node {
*   data: 2,
*   left: Node { data: 1, left: null, right: null },
*   right: null
* },
* right: Node {
*   data: 5,
*   left: Node { data: 4, left: null, right: null },
*   right: Node {
*     data: 6,
*     left: null,
*     right: Node { data: 7, left: null, right: null }
*   }
* }
* }
*/
treeHeight(root); // 3

tree-printer.js

function printTree(root){
  if (!root) { return ''; }
  let output = []; // each subarray is a row
  let rowIndex = 0;
  let checkNodes = [];
  checkNodes.push(root);
  while (checkNodes.length > 0) {
    if (!output[rowIndex]) { output.push([]); }
    let checkNodesNext = [];
    for (let i = 0, max = checkNodes.length; i < max; i++) {
      const n = checkNodes[i];
      output[rowIndex].push(n.value);
      checkNodesNext = checkNodesNext.concat(n.children);
    }
    checkNodes = checkNodesNext.slice(0);
    rowIndex++;
  }
  output = output.map(item => item.join(' '));
  return output.join('\n');
}

const Node = function (value, children) {
  this.value = value;
  this.children = (children) ? children : [];
}

// TEST

const B = new Node('B'); 
const C = new Node('C'); 
const A = new Node('A', [B, C]);
const E = new Node('E', [A]);
const F = new Node('F', [new Node('R'), new Node('J')]);

const tree = new Node('D', [E, F, new Node('G')])

printTree(C); // 'C'
printTree(A); // 'A\nB C'
printTree(tree); // 'D\nE F G\nA R J\nB C'