Slice and Dice a Binary Tree

Hierarchical data are ubiquitous. This makes understanding the techniques on how to process them all the more important. The three standard algorithms are pre-order, in-order, and post-order traversals. This post will look at the mentioned techniques and a few others that will group hierarchical data by rows and columns. We will also explore the top, bottom, right, and left views of a tree.

PreOrder, InOrder, and PostOrder Traversals

Starting with the standard depth-first traversals, we have pre-order, in-order, and post-order as follows. In depth-first traversal, the algorithm is encouraged to go as far into one branch as possible before backtracking.

// PreOrder
const preorder = (root) => {
  if (!root) return;
  console.log(root.val);
  preorder(root.left);
  preorder(root.right);
}

// InOrder
const inorder = (root) => {
  if (!root) return;
  preorder(root.left);
  console.log(root.val);
  preorder(root.right);
}

// PostOrder
const postorder = (root) => {
  if (!root) return;
  preorder(root.left);
  preorder(root.right);
  console.log(root.val);
}

GroupByDepth

Next, we have level-order or group-by-depth. If we only care about printing the node values, then the traditional level-order traversal will do the job. To group the nodes by level, any of the standard depth-first traversals can be used in conjunction with a map of level to list of nodes. A level tracker is also used to track the depth as the algorithm proceeds each subtree.

// GroupByDepth
const groupByDepth = (root) => {
  if (!root) return;
  const levelMap = {};
  groupByDepthHelper(root, levelMap, 0);
  Object.values(levelMap).forEach(nodeVals => console.log(nodeVals.join('')));
}

const groupByDepthHelper = (root, map, level) => {
  if (!root) return;
  map[level]?.push(root.val) || (map[level] = [root.val]);
  groupByDepthHelper(root.left, map, level + 1);
  groupByDepthHelper(root.right, map, level + 1);
}

GroupByColumn

Vertical-order, or group-by-column, follows a similar implementation to level-order except for one key difference. Instead of tracking depth during the recursive calls, we will add one if we go to the right subtree, and subtract one if we go to the left subtree.

// GroupByColumn
const groupByColumn = (root) => {
  if (!root) return;
  const vLevelMap = {};
  groupByColumnHelper(root, vLevelMap, 0);
  Object.values(vLevelMap).forEach(nodeVals => console.log(nodeVals.join('')));
}

const groupByColumnHelper = (root, map, vLevel) => {
  if (!root) return;
  map[vLevel]?.push(root.val) || (map[vLevel] = [root.val]);
  groupByColumnHelper(root.left, map, vLevel - 1);
  groupByColumnHelper(root.right, map, vLevel + 1);
}

Top, Bottom, Left, and Right Views

Lastly, getting the right side view of a tree can be done by using one of the depth-first traversals and leveraging the level data to either put the value into a map if it is the first time the level is visited or override the value if the level has been visited before. As the depth-first traversal moves from left to right, the value at the level is overridden until the right-most values remain. Getting the left side view can be accomplished by reversing the traversal order. Getting the top or bottom view relies on the vertical level rather than the depth info.

// GetRightView
const getRightView = (root) => {
  if (!root) return;
  const map = {};
  getRightViewHelper(root, map, 0);
  console.log(Object.values(map).join(''));
}

const getRightViewHelper = (root, map, level) => {
  if (!root) return;
  map[level] = root.val;
  getRightViewHelper(root.left, map, level + 1);
  getRightViewHelper(root.right, map, level + 1);
}