Reversing Those Binary Trees: A Recursive Romp into Node Land

Sometimes, in the swirling vortex of coding interviews and hush-hush gossip about “famous tech companies renowned for their engineering,” you might hear a mythical question: “Could you, on a whiteboard, reverse a binary tree for us?” And if you’re like me, you’ll pause, maybe gulp, and wonder if you missed the day in Computer Science 101 when that was taught as essential survival knowledge. Fortunately, I haven’t had to perform this wizardry in a real-life interview—so I figured I’d put my pride on the line, test my mettle, and see if I could pull it off without crying in front of a hypothetical interviewer¹.

---

A Quick Refresher: What Even Is a Binary Tree?

A Binary Tree is that delightfully simple data structure where each node can have up to two children (left and right). People like to get fancy and call it a “rooted binary tree” or a “bifurcating arborescence” (the latter presumably for when you want to sound extra academic). Yet the concept is straightforward: each node has a value, plus these left and right pointers, each of which can lead to another node.

You can do all sorts of fun stuff with binary trees—Git, for instance, uses graph-like structures for commits, and Facebook employs clever data structures for search. It’s also the pattern we use for good ol’ family trees, though hopefully your actual family tree is balanced and not branched by scandal.

Let’s Build a Node (in Very Literal Code)

We can define a node creation function in JavaScript like so:

const node = (value, left, right) => [value, left, right];

Yes, we’re just using an array of three elements—because it’s easy and we’re not picky. For serious, production-level code, you’d probably want something more robust. But if you’re just messing around, this is enough.

Here’s a sample tree:

const tree = () => node(
  \"a\",
  node(\"b\", node(\"d\"), node(\"e\")),
  node(\"c\", node(\"f\"), node(\"g\")),
);

Under the hood, this yields:

[
  \"a\",
  [\"b\", [\"d\", null, null], [\"e\", null, null]],
  [\"c\", [\"f\", null, null], [\"g\", null, null]]
]

Not as pretty as the ASCII diagrams you see in textbooks, but it works.

---

The Great Reverse (a.k.a. Mirror) Operation

Now, reversing a binary tree basically means creating its mirror image: all left children become right children and vice versa. Hypothesis: just flip left and right for every node, right? Indeed. Let’s pick a strategy. We could do this iteratively, but let’s go with recursion, because recursion is both elegant and a little bit magical².

A Quick Detour: Traversal

Before we reverse anything, let’s recall that we often traverse the tree—say to print out each node’s data. For example:

const traverse = ([data, left, right]) => {
  console.log(data);
  if (left) traverse(left);
  if (right) traverse(right);
  return [data, left, right];
};

It’s basically a depth-first approach. We’re using destructuring in the function parameters. If left or right is null, we skip them. Then we return an array that still has the same shape.

The Actual Reversal

To mirror the tree, we just do this:

const reverse = ([data, left, right]) => [
  data,
  right && reverse(right),
  left && reverse(left),
];

Notice: the second slot is right reversed, and the third slot is left reversed. That’s the entire trick. Now if you log out reverse(tree()), you’ll see a new tree with the left and right children swapped at every level.

// [ 'a',
//   [ 'c',
//     [ 'g', undefined, undefined ],
//     [ 'f', undefined, undefined ]
//   ],
//   [ 'b',
//     [ 'e', undefined, undefined ],
//     [ 'd', undefined, undefined ]
//   ]
// ]

Yes, we have accomplished the fabled “reverse a binary tree” feat. Cue applause from your fictional interview panel.

---

But What About Balance?

Balanced vs. Unbalanced

A balanced binary tree is one in which the nodes fill up level by level, with no large gaps in the distribution of children. An unbalanced tree might have a node with a left child that goes three levels deep while the right side is empty. Or in everyday terms, it’s a lopsided structure that can cause performance woes.

Checking Balance with Depth

One naive approach: find the max depth and min depth of your tree, then see if they differ by more than 1. If the difference is greater than 1, we say the tree is unbalanced.

We can define:

const depth = (maxOrMin, [_, left, right]) =>
  1 + Math[maxOrMin](
    left ? depth(maxOrMin, left) : 0,
    right ? depth(maxOrMin, right) : 0
  );

const maxDepth = tree => depth(\"max\", tree);
const minDepth = tree => depth(\"min\", tree);

We skip the node’s data (using _) because we only care about whether there’s a node or not. Then:

const isBalanced = tree =>
  minDepth(tree) >= maxDepth(tree) - 1;

And voila: you can quickly check whether your tree is balanced³.

---

Building a Searchable Tree

Insert (Push) Operation

Let’s say we want to store a set of unique numbers in a binary search tree. We can define a push function:

const push = (value, [data, left, right] = []) =>
  !data
    ? node(value)
    : value < data
      ? left
        ? [data, push(value, left), right]
        : [data, node(value), right]
      : right
        ? [data, left, push(value, right)]
        : [data, left, node(value)];

1. If there’s no data, we create a new node with our value.
2. Otherwise, we check if value is less than data. If so, we try to store it on the left. If the left node is missing, we put it there directly. If not, we recursively call push deeper.
3. Similarly for the right side.

This is a simplistic BST insertion, but it does the job for our purposes. Testing:

let myTree = push(20);
myTree = push(10, myTree);
myTree = push(30, myTree);
myTree = push(11, myTree);
myTree = push(9, myTree);

We get a nice tree structure with 20 as the root, 10 on the left (which itself has a 9 and 11), and 30 on the right⁴.

---

Concluding Thoughts (and Encouragement to Tinker)

In this little expedition, I took a whack at reversing a binary tree (the infamous interview question) and dabbled in checking for balance, plus building a simple BST. Each snippet is a tiny window into the wonders of recursion, composition, and data structures. Sure, a real production environment might require more robust logic and stricter type safety. But for a personal exploration or quick interview brush-up, this is enough to sharpen your wits.

If you’re hungry for more, consider:

• Search Functions: e.g., finding the highest or lowest number in the tree.
• Median or Self-Balancing: you can get fancy, rearranging nodes so the tree remains balanced automatically.

At the end of the day, I find that playing around with trees is a gentle exercise in rethinking how data flows, how recursion simplifies code, and how a few mental leaps can make you look dangerously cool in those dreaded whiteboard interviews. So if you’ve followed along this far, go forth and push (or pop) some data! The more you practice, the less likely you’ll be caught off-guard by the next “flip this binary tree” request from a big-name recruiter. And who knows, you might just come to love the symmetry and elegance of a well-crafted binary structure.

---

¹ Possibly with them smirking while drawing big red X’s over your code.
² Or maddening, if you’re not a recursion fan—some folks just want iterative loops for everything. This can be truly enlightening².
³ In practice, self-balancing trees (like AVL or Red-Black Trees) maintain near-optimal balance automatically, but that’s a deeper rabbit hole.
⁴ For real scenarios, you’d want error-checking for duplicates or a more robust structure, but we can skip that here, because we’re just exploring.