CODEWITHSUNDEEP
algorithmtree
PoorGuy
PoorGuy

Reputation: 29

Tree from balanced parenthesis

I have to find height of tree and find protection number (or just to generate a tree) from balanced parentheses. For example:
()()()() creates tree like a list with height 3.
I have no idea how to convert parentheses to tree. I found some 'answers':
http://www.cs.utsa.edu/~wagner/knuth/fasc4a.pdf (second page contains all examples for tree with 4 nodes)
paragraph - Binary Trees, Forests, Non-Crossing Pairs :
https://sahandsaba.com/interview-question-generating-all-balanced-parentheses.html
However, I still don't know how to create a tree from such defined parentheses. I have some impression that in Knuth, authors treat it as something obvious.
Do I miss something or it's not that simple?
Is it necessary to create a forest and then a binary tree?

Upvotes: 0

Views: 2430

Answers (2)

trincot
trincot

Reputation: 350290

A pair of parentheses represents a node. What appears within those parentheses represents its left child's subtree (according to the same rules). What appears at the right of those parentheses represents the node's right child's subtree (again, according to the same rules).

The conversion of this encoding into a binary tree can be done recursively like this:

function makeBinaryTree(input):
    i = 0 # character index in input

    function recur():
        if i >= input.length or input[i] == ")":
            i = i + 1
            return NIL
        i = i + 1            
        node = new Node
        node.left = recur()
        if i >= input.length or input[i] == ")":
            i = i + 1
            return node
        node.right = recur()
        return node

    return recur()

Here is an implementation in JavaScript that performs the conversion for each of those 4-noded trees, and pretty prints the resulting trees:

function makeBinaryTree(input) {
    let i = 0; // character index in input
    return recur();
    
    function recur() {
        if (i >= input.length || input[i++] === ")") return null;
        let node = { left: recur(), right: null };
        if (i >= input.length || input[i] === ")") {
            i++;
            return node;
        }
        node.right = recur();
        return node;
    }
}

// Helper function to pretty print a tree
const disc = "\u2B24";
function treeAsLines(node) {
    let left = [""], right = [""];
    if (node.left) left = treeAsLines(node.left);
    if (node.right) right = treeAsLines(node.right);
    while (left.length < right.length) left.push(" ".repeat(left[0].length));
    while (left.length > right.length) right.push(" ".repeat(left[0].length));
    let topLeft = "", topRight = "";
    let i = left[0].indexOf(disc);
    if (i > -1) topLeft = "┌".padEnd(left[0].length-i+1, "─");
    i = right[0].indexOf(disc);
    if (i > -1) topRight = "┐".padStart(i+2, "─");
    return [topLeft.padStart(left[0].length+1) + disc + topRight.padEnd(right[0].length+1)]
           .concat(left.map((line, i) => line + "   " + right[i]));
}

// The trees as listed in Table 1 of http://www.cs.utsa.edu/~wagner/knuth/fasc4a.pdf
let inputs = [
    "()()()()",
    "()()(())",
    "()(())()",
    "()(()())",
    "()((()))",
    "(())()()",
    "(())(())",
    "(()())()",
    "(()()())",
    "(()(()))",
    "((()))()",
    "((())())",
    "((()()))",
    "(((())))"
];

for (let input of inputs) {
    let tree = makeBinaryTree(input);
    console.log(input);
    console.log(treeAsLines(tree).join("\n"));
}

Upvotes: 3

Rigel Bezerra de Melo
Rigel Bezerra de Melo

Reputation: 111

If I understood Knuth correctly, the representation works as the following: A pair of matching parentheses represents a node, e.g. () = A. Two consecutive pairs of matching parentheses means that the second node is the right child of the first one, e.g. ()() = A -> B. And two pairs of embedded parentheses means the inside node is the left child of the outside node, i.e. (()) = B <- A. Therefore, ()()()() = A -> B -> C -> D.

A possible algorithm to convert parentheses to binary tree would be:

convert(parentheses):
  if parentheses is empty:
    return Nil

  root = Node()

  left_start = 1
  left_end = Nil

  open = 0
  for p = 0 to |parentheses|-1:
    if parentheses[p] == '(':
      open += 1
    else
      open -= 1

    if open == 0:
      left_end = p
      break

  root.left = convert(parentheses[left_start:left_end] or empty if index out of bound)
  root.right = convert(parentheses[left_end+1:] or empty if index out of bound)

  return root

It works by converting parentheses (L)R in the binary tree L <- A -> R recursively.

Upvotes: 2

Related Questions