Inverting a binary tree: probably easier than you think
Spiciness: 🌶️🌶️ (poblano)
Problem Statement
Write a function which takes in a binary tree, inverts it, and returns the inverted tree.
An inverted version of the tree above would swap every left node in the tree for its corresponding right node.
1class BinaryTree {2 constructor(value) {3 this.value = value4 this.left = null5 this.right = null6 }7}8/*9 INPUT10
11 112 / \ 13 2 3 flip me!14 / \ / \15 4 5 6 716 / \17 8 9 18
Look down at your palms - they're mirror images of each other with respect to an imaginary line between your pinkies:
1/* INPUT | SOLUTION2 |3 1 | 1 4 / \ | / \ 5 2 3 flip 3 26 / \ / \ -> / \ / \7 4 5 6 7 | 7 6 5 48 / \ | / \9 8 9 | 9 8 10 |11
tl;dr
- The solution is as simple as reassigning left & right pointers between nodes in one pass.
- Traversing a tree like this requires a queue to go breadth first instead of depth first.
- Leaf nodes' children, for the purposes of the queue, can be
null
; .This is important for space complexity calculations later.
Solution
Brief
Linked lists, trees, BSTs are often easy problems masquerading as difficult ones.
You may feel an inkling to traverse the tree depth-first (1 -> 2 -> 4) and re-construct the tree backwards somehow or traverse in some nebulous "opposite" fashion. However, the final tree is mirrored with respect to Y axis, not X. That should be a hint you're going in the wrong direction (up/down vs left/right)
Turns out, all you'll need is queue to parse the tree left to right, swapping each node's left and right values along the way.
A binary tree's node only has so much to offer. You havenode.value
, node.left
and node.right
:
1/* 1 1 2 / \ / \ 3 2 3 flip 3 24
Once you have that, you're done. Well, almost: you need to figure out how to apply the same actions to node 2, node 3, their children, and so on.
Traverse left-to-right (breadth-first)
First, let's look at how to output the value of every "level" of a tree, left-to-right. As neat as recursion is, I think iterative solutions are easier to read:
1function printBinaryTreeValues(tree) {2 // initialize the queue. Our first element is the root3 const queue = [tree]4 5 // we'll be updating this guy as we go in lieu of using a recursive function6 let currentNode7
8 // while there something in the queue...9 while (queue.length > 0) {10 // yeet first item from the queue11 currentNode = queue.shift()12
13 // do something with node, in this case, print14 console.log(currentNode.value)15
16 // update the queue to handle the children nodes17 if (currentNode.left) queue.unshift(currentNode.left)18 if (currentNode.right) queue.unshift(currentNode.right)19
20 // next iteration will handle the newly added children 21 // preserving the left-to-right direction22 }23 // here, we are out of queue items24}25
Let's go back to our smallest node "unit"...
Swapper helper function
1/* 12 / \3 2 34
Now you swap nodes with values 2 and 3. This logic will be applied to their children too, but for now, we're only looking at this one piece. Always be on the lookout as to what logic can be pawned off to its own function: don't clutter the meat of the solution or you may come to regret it. That regret comes when you're about 80% finished confidently explaining your way through a whiteboard problem.
Quickly swap values:
1// chad ES6 swap:2function swapNodeLeftAndRight(node) {3 [node.left, node.right] = [node.right, node.left]4}5// ugly, oldschool swap:6function swapNodeLeftAndRight(node) {7 const tempLeft = node.left8 node.left = node.right9 node.right = tempLeft10}11
Completed solution
Finally, here is our iterative solution: (parse, swap left & right, enqueue children)
1// This is the class of the input binary tree.2class BinaryTree {3 constructor(value) {4 this.value = value5 this.left = null6 this.right = null7 }8}9
10function swapLeftAndRight(node) {11 [node.left, node.right] = [node.right, node.left]12}13
14function invertBinaryTree(tree) {15 const queue = [tree]16 let currentNode17 while (queue.length > 0) {18 currentNode = queue.shift()19 if (currentNode) swapLeftAndRight(currentNode)20 if (currentNode.left) queue.unshift(currentNode.left)21 if (currentNode.right) queue.unshift(currentNode.right)22 }23 }24
Big O: Time & Space Complexity
Since this algorithm runs in one pass through all the tree's nodes (no nested loops, or other shenanigans) the time complexity is O(n).
As for space complexity - there's a queue growing in memory with every iteration. There's a little nuance to why this is so (touched on in the tl;dr) but the answer is O(n) as well, not O(1)