String representation of Binary Tree, find most distant from the tree root

Question

This is an algorithm that I was given a while ago for a test and I couldn't figure it out. Any ideas?

You are given a recursive notation of a binary tree: each node of a tree is represented as a set of three elements:

1. value of the node
2. left subtree
3. right subtree

So, a tree can be written as (value left_subtree right_subtree).

If a node doesn't exist then it is represented as an empty set: ().

Your task is to obtain a list of nodes, that are the most distant from the tree root, in the order from left to right.

In the notation of a node its value and subtrees are separated by exactly one space character.

Example:

//             2
//            / \
//           /   \
//          /     \
//         /       \
//        /         \
//       7           5
//      / \           \
//     /   \           \
//    2     6           9
//         / \         /
//        /   \       /
//       5     11    4

tree = "(2 (7 (2 () ()) (6 (5 () ()) (11 () ()))) (5 () (9 (4 () ()) ())))"
treeBottom(tree) // Desired output: [5, 11, 4].

Answer 1

Probably not most sophisticated solution, but it works..

var tree = "(2 (7 (2 () ()) (6 (5 () ()) (11 () ()))) (5 () (9 (4 () ()) ())))";

var level = 0;
var rootLeafs = []
var leaf = -1;
var i;

var parseToken = {
  "(": enterLevel,
  ")": leaveLevel,
  " ": separate,
}

function isValidTreeElement() {
  applyFn = parseToken[tree[i]]||parseNumber;
  return applyFn()
}

function enterLevel() {
  if (i > 0 && tree[i-1] != " ") {
    alert("Nodes must be separated by space");
    return false;
  }

  level++;
  // entering new root leaf
  if (level == 2) {
    leaf++;
    rootLeafs[leaf] = [];
  }
  return true;
}

function leaveLevel() {
  level--;
  return true;
}

function separate() {
  if (i > 0 && tree[i-1] == " ") {
    alert("Multiple spaces in row");
    return false;
  }
  return true;
}

function parseNumber() {
  var advance = tree.substring(i).indexOf(" ");
  if (advance < 1) {
    alert("Number must followed by space");
    return false;
  }
  var num = Number(tree.substring(i,i+advance));
  if (isNaN(num)) {
    alert("Expected number, given: " + tree.substring(i,i+advance));
    return false;
  }
  i += advance - 1; // move index to last char of number
  // add value to current leaf level
  if (level > 1) {
    try {
      rootLeafs[leaf][level-2].push(num);
    } catch(e) {
      rootLeafs[leaf][level-2] = [num];
    }
  }
  return true;
}

function walk() {
  for (i = 0; i < tree.length; i++) {
    if (!isValidTreeElement()) {
      return;
    }
  }

  // get last level from each root leaf
  var results = rootLeafs.reduce(function(a, b) {
    return a.concat(b.slice(-1)[0]);
  }, []);

  console.log('Result: ' + results);
}

walk();