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:

value of the node
left subtree
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].

Besides from the fact that this is not a binary-search-tree at all, what have you tried so far and where are you stuck? Can you include your code in the question? — Marco
Each level of parentheses is another step away from the root. So the non-empty node (or nodes) at the deepest nesting level is the furthest from the root. So if you were to keep track of the current nesting level as well as the current deepest node, you could do this in a single scan of the string. — Jim Mischel

bigless bigless · Accepted Answer · 2017-09-15T00:33:58

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();

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

1 Answers