Tree serialization and deserialization

test.js

const Tree = require('./Tree')

// -------------------------
// Given a tree structure as depicted below:
//
//             A
//            / \ \
//           B  C  D
//          / \  \  \
//         E  F   G  H
//        /
//       I

// Construct tree1 via addConnection()
var tree1 = new Tree()
tree1.addConnection('AB')
tree1.addConnection('AC')
tree1.addConnection('AD')
tree1.addConnection('BE')
tree1.addConnection('BF')
tree1.addConnection('CG')
tree1.addConnection('DH')
tree1.addConnection('EI')

console.log('tree 1 node walk:')
tree1.walk('A', console.log)
const treeStr1 = tree1.serialize()
console.log(`tree 1 serialized as: ${treeStr1}`)

// Construct tree2 via treeStr1
const tree2 = tree1.deserialize(treeStr1)
console.log('\ntree 2 node walk:')
tree2.walk('A', console.log)
const treeStr2 = tree2.serialize()
console.log(`tree 2 serialized as: ${treeStr2}`)

if (treeStr1 === treeStr2) {
  console.log('\nPASS: 2 serialzed strings match')
} else {
  console.log('\nFAIL: 2 serialzed strings don\'t matched')
}

Tree.js

class Tree {
  /*
   * Construct an empty tree
   */
  constructor () {
    this.connections = {}
  }

  /*
   * Return a ';' delimited string with each component
   * represents a parent and its child nodes. Parent node
   * is the first character, then child nodes follows.
   */
  serialize() {
    const strArr = []
    Object.keys(this.connections).forEach(parent => {
      if (this.connections.hasOwnProperty(parent)) {
        const childrenStr = this.connections[parent].join('')
        console.log(parent + childrenStr)
        strArr.push(parent + childrenStr)
      }
    })
    return strArr.join(';')
  }

  /*
   * Given a serialized string, returns a corresponding Tree object.
   */
  deserialize(str) {
    const strArr = str.split(';')
    const newTree = new Tree()
    strArr.forEach(str => {
      const parent = str[0]
      if (newTree.connections[parent] === undefined) {
        newTree.connections[parent] = []
      }
      const childrenStr = str.slice(1)
      for (var i=0; i<childrenStr.length; i++) {
        // console.log(`add to parent ${parent} child ${childrenStr[i]}`)
        newTree.connections[parent].push(childrenStr[i])
      }
    })
    return newTree
  }

  /*
   * Helper function - Given a 2-letter string with the first letter
   * represents the parent node, and the second represents the child,
   * establish a parent-child connection between them.
   */
  addConnection(pc) {
    const parent = pc[0]
    const child = pc[1]
    if (this.connections[parent] === undefined) {
      this.connections[parent] = []
    }
    if (this.connections[child] === undefined) {
      this.connections[child] = []
    }
    this.connections[parent].push(child)
  }

  /*
   * Helper function - Transverse the tree starting at node,
   * at each child node, invoke callback(parent + child)
   */
  walk(node, callback) {
    const que = []
    const visited = {}
    que.push(node)
    visited[node] = true  // bookkeep visited nodes

    while (que.length > 0) {
      const parent = que.shift()
      this.connections[parent].forEach(child => {
        if (visited[child] === undefined) {
          que.push(child)
          visited[child] = true
          callback(parent + child)
        }
      })
    }
  } // walk
} // Tree

module.exports = Tree