JavaScript Tree Data Structure

by Bret Lowrey

HTML

<script src="https://wzrd.in/standalone/expect@latest"></script>
<body>

</body>

JavaScript

const getNode = (tree, k) => {
  if (tree === null) {
    return null;
  }
  return {
    key: k,
    children: tree[k]
  };
};

const search = tree => (toFind, method = 'DFS') => {
  const root = Object.keys(tree)[0];
  let nodes = [getNode(tree, root)];
  while (nodes.length > 0) {
    let n = nodes.pop();
    if (n.key === toFind) {
      return n;
    }
    if (n.children !== null) {
      Object.keys(n.children).forEach(child => {
        if (method === 'DFS') {
          nodes.push(getNode(n.children, child));
        } else {
          nodes.unshift(getNode(n.children, child));
        }
      });
    }
  }
  return null;
};

const testTree = {
  0: {
    1: {
      3: {
        6: null,
        7: null
      },
      5: {
        8: null
      }
    },
    2: {
      4: null
    }
  }
};

expect(search(testTree)('-1')).toEqual(null);
expect(search(testTree)('3').children).toEqual({6: null, 7:null});

document.body.innerHTML = 'All tests passed.'