Rally Binary tree question

rally-btree-serialize-post-interview.js

//// POST INTERVIEW VERSION
// NOTE Rado, Yi: I took the code where I left off and got it working in this second Gist file. It's probably not
// the most elegant solution, but it works. The code as of the end of the interview is in the other Gist.

// Given a binary tree, how would you serialize it into a string?

//Example input
var input = {
  value: "a",
  left: {
    value: "b",
  },
  right: {
    value: "c",
    left: {
      value: "d",
    },
    right: {
      value: "e",
    },
  },
};

//example output
// a(b)(c(d)(e))

const assert = ({ given, should, actual, expected }) => {
  const stringify = (value) =>
    Array.isArray(value)
      ? `[${value.map(stringify).join(",")}]`
      : `${JSON.stringify(value)}`;

  const actualString = stringify(actual);
  const expectedString = stringify(expected);

  if (actualString === expectedString) {
    console.log(`OK:
    given: ${given}
    should: ${should}
    actual: ${actualString}
    expected: ${expectedString}
    `);
  } else {
    throw new Error(`NOT OK:
    given ${given}
    should ${should}
    actual: ${actualString}
    expected: ${expectedString}
    `);
  }
};

const toString = (tree) => {
  let node = tree;
  let { value, left, right } = node;

  let out = "";

  out += value;
  if (left) {
    out += `(${toString(left)})`;
  }
  if (right) {
    out += `(${toString(right)})`;
  }
  return out;
};

const toTree = (str) => {
  let depth = 0;
  let value;
  let buffer = "";
  let leftBuffer = "";
  let rightBuffer = "";

  for (let i = 0, char; i < str.length; i++) {
    char = str[i];
    if (char === "(") {
      if (depth > 0) {
        buffer += char;
      }
      depth++;
    } else if (char === ")") {
      depth--;
      if (depth === 0) {
        if (!leftBuffer) {
          [leftBuffer, buffer] = [buffer, ""];
        } else if (leftBuffer && !rightBuffer) {
          [rightBuffer, buffer] = [buffer, ""];
        }
      } else {
        buffer += char;
      }
    } else {
      if (depth > 0) {
        buffer += char;
      } else {
        value = char;
      }
    }
  }

  return Object.assign(
    { value },
    leftBuffer ? { left: toTree(leftBuffer) } : null,
    rightBuffer ? { right: toTree(rightBuffer) } : null
  );
};

assert({
  given: "a binary tree",
  should: " render the expected string output",
  actual: toString(input),
  expected: "a(b)(c(d)(e))",
});

assert({
  given: "a serialized binary tree string",
  should: "return the parsed binary",
  actual: toTree(toString(input)),
  expected: input,
});

rally-btree-serialize.js

//// SUBMITTED DURING INTERVIEW
// NOTE Rado, Yi: I got the algorithm working after the interview. The implementation with the passing tests is
// in the second file in this Gist. It's probably not the most elegant solution, but it works.

// Given a binary tree, how would you serialize it into a string?

//Example input
var input = {
  value: 'a',
  left: {
  	value: 'b'
  },
  right: {
  	value: 'c',
    left: {
    	value: 'd'
    },
    right: {
    	value: 'e'
    }
  }
};

//example output
// a(b)(c(d)(e))

const assert = ({ given, should, actual, expected }) => {
  const stringify = (value) =>
    Array.isArray(value)
      ? `[${value.map(stringify).join(",")}]`
      : `${JSON.stringify(value)}`;

  const actualString = stringify(actual);
  const expectedString = stringify(expected);

  if (actualString === expectedString) {
    console.log(`OK:
    given: ${given}
    should: ${should}
    actual: ${actualString}
    expected: ${expectedString}
    `);
  } else {
    throw new Error(`NOT OK:
    given ${given}
    should ${should}
    actual: ${actualString}
    expected: ${expectedString}
    `);
  }
};


const toString = tree => {
    let node = tree;
    let { value, left, right } = node;
    
    let out = '';
    
    out += value;
    if (left) {
        out += `(${toString(left)})`
    }
    if (right) {
        out += `(${toString(right)})`
    }
    return out;
};

const toTree = str => {
    let node = {};
    let inLeft = false;
    let inRight = false;
    let leftString = '';
    let rightString = '';

    for (let i = 0, char; i < str.length ; i++) {
        char = str[i];
        if (char === '(') {
            if (!inLeft) {
                inLeft = true;
            }
            if (!inRight && leftString) {
                inRight = true;
            }
        } else if (char === ')') {
            if (inLeft) {
                inLeft = false;
            }
            if (inRight) {
                inRight = false;
            }
        } else if (inLeft) {
            leftString += char;
        } else if (inRight) {
            rightString += char;
        } else {
            node.value = char;
        }
    }

    return Object.assign(
        node,
        leftString ? { left: toTree(leftString) } : null,
        rightString ? { right: toTree(rightString) } : null
    );
};

assert({
    given: 'a binary tree',
    should: ' render the expected string output',
    actual: toString(input),
    expected: 'a(b)(c(d)(e))',
});

assert({
    given: 'a serialized binary tree string',
    should: 'return the parsed binary',
    actual: toTree(toString(input)),
    expected: input,
});

hey Matt, thanks for posting the solution afterwards! Im taking it into account, and I mentioned it to the rest of the panel

Awesome! Thanks for letting me know, Rado.