The author of Homebrew was recently asked to “invert a binary tree” during a Google interview. Well, he didn’t get the job, and many a blogger cried foul at the pitiful state of technical interviews. I agree that coding interviews can be arbitrary and asinine—but I couldn’t help myself. I had to take the binary tree challenge to validate my existence as a programmer.
Do what now?
Technical interview questions are often vague by design: the interviewer wants you to ask clarifying questions and get a feel for your approach to problem solving. If your first question is “what be this binary tree witchcraft?”, then the smugly satisfied interviewer can start checking his email or whatever while you fumble with dry erase markers or slowly back out of the room.
My first question to the interviewer would’ve been “what do you mean by invert?” I don’t have a Googler sitting across the table from me right now, so I’ll assume the worst.
Maybe this was a problem of converting a max-heap to a min-heap, or vice versa. If that was true, I might’ve turned a shade or two whiter than the board while trying to derive heap sort from memory. Thankfully I can crank out some mediocre F# solution in my spare time, without the heart palpitations.
I’d ask if the input tree would be represented in array form, and of course it would because the Googler likes fast random access and cache locality. But if we want to represent the tree hierarchically, we should define a
type Tree<'a> = | Leaf of 'a | Node of Tree<'a> * Tree<'a>
This can represent a tree but it requires each node to have two children—it doesn’t cover the case where a Node has only one child. Let’s try a different definition:
type Tree<'a> = | Nub | Node of 'a * Tree<'a> * Tree<'a>
This one can represent the case where a
Node has only one child, i.e.
Node(1, 2, Nub) where
1 is the parent and
2 is the left child. In the case where single-child
Node children must be to the left, this definition unfortunately allows invalid state to be represented, i.e.
Node(1, Nub, 2).
A definition like the following might make that invalid state unrepresentable:
type Tree<'a> = | Leaf of 'a | Node of Tree<'a> * Tree<'a> option
But we’ll go with the second
Tree definition because
Nub sounds cool and I’m not too concerned about the strictness because we know we’re building the tree correctly, right?
Indexing into a binary heap array
Since we’re assuming an array representation, we need to be able to find the indices of children of any given node. Imagine a binary tree consisting of one parent
1, a left child
2 and a right child
3. This would be an array
[1, 2, 3]. Simple enough, but how do you arrange elements when you have more than three nodes? You could read the dense Wikipedia explanation for this, or you could define these two functions:
/// Gets the array index of an element's left child node let inline leftLeaf n = (n * 2) + 1 /// Gets the array index of an element's right child node let inline rightLeaf n = (leftLeaf n) + 1
Here we are saying that a node’s left child node can be found by doubling the node’s array index and adding 1, and the left child’s sibling is always its direct successor.
Growing the tree
Now we can write a function that takes an array and builds a
let treeify (a:_) = let rec loop pos = match (pos, a.Length) with | BranchesBoth -> let leftBranch = loop (leftLeaf pos) let rightBranch = loop (rightLeaf pos) Node(a.[pos], leftBranch, rightBranch) | BranchesLeft -> let leftBranch = loop (leftLeaf pos) Node(a.[pos], leftBranch, Nub) | IsLeaf -> Node(a.[pos], Nub, Nub) loop 0
Here we are recursively constructing the tree from top (
loop 0) to bottom. Notice the use of pattern matching to determine how we descend the tree. You could implement this function without pattern matching, but it wouldn’t look as pretty and you wouldn’t feel as smart. This is the definition for the pattern:
let (|IsLeaf|BranchesLeft|BranchesBoth|) (pos, len) = if rightLeaf pos < len then BranchesBoth else if leftLeaf pos < len then BranchesLeft else IsLeaf
This pattern defines the three ways in which our tree can grow from the current
- Current node has two children
- Current node has only one (left) child
- Current node has no children
Let’s put it to the test against a randomly generated array:
let rng = new Random() let values = [| for n in 1 .. 10 -> rng.Next 100 |] let tree = treeify values
You might see some output like this:
val values : int  = [|80; 60; 56; 7; 3; 4; 89; 79; 71; 19|] val tree : Tree<int> = Node (80, Node (60,Node (7,Node (79,Nub,Nub),Node (71,Nub,Nub)), Node (3,Node (19,Nub,Nub),Nub)), Node (56,Node (4,Nub,Nub),Node (89,Nub,Nub)))
You could say this tree is only slightly more readable than the array representation. Let’s write a function to pretty print our tree:
let prettyPrint tree = let rec loop tree depth = let vine = String('-', depth) match tree with | Node (n, l, r) -> printfn "|%s%A" vine n loop l (depth + 1) loop r (depth + 1) | Nub -> ignore() loop tree 0
A little more pattern matching and recursion produces a tree that wouldn’t exactly impress Bob Ross, but it’s intelligible:
|80 |-60 |--7 |---79 |---71 |--3 |---19 |-56 |--4 |--89
Sorting the tree
We’ve been working backwards and probably won’t be getting a “yes” from the interviewer, but we can’t stop now. Let’s write heapsort in F#. First we’ll need a function to “heapify” sections of our array:
let heapify (a:_) cmp start len = let rec loop node = let left = leftLeaf node if left < len then let child = pickBestChild a node cmp len if cmp a.[node] a.[child] < 0 then swap a node child loop child loop start
We descend the tree node by node, checking to make sure it’s in heap order. If we find that a node’s child outranks its parent, we swap them.
cmp is a function that compares two values and returns -1, 0, or 1; this predicate is what will determine whether we’re building a min- or max-heap. Let’s define some of the functions that
/// Picks the child index of an element satisfying the comparator let inline pickBestChild (a:_) n cmp len = let left = leftLeaf n let right = rightLeaf n if right < len && cmp a.[left] a.[right] < 0 then right else left /// Swaps two elements of an array let swap (a:_) i j = let temp = a.[i] a.[i] <- a.[j] a.[j] <- temp let cmp<'a> x y = Comparer<'a>.Default.Compare(x, y)
Without further ado, an actual sort function:
let heapSort (a:_) cmp = let len = a.Length let heapify = heapify a cmp let lastParent = (len / 2) - 1 for node = lastParent downto 0 do heapify node len for lastNode = len - 1 downto 1 do swap a lastNode 0 heapify 0 lastNode
3 we partially apply the heapify function with the arguments that will stay the same, creating a shorthand for slightly easier reading. On line
4 we’re calculating the index of the last parent node in the array. On lines
6 we run a loop that heapifies every node from the last parent up to the first node of the tree. This has the effect of iteratively pushing the min (or max, depending on your
cmp function) value to the top of the heap.
9 we take advantage of the heap property that the min (or max) value is always at the top of the heap. We can produce a sorted array by taking the value off the top of the heap and putting it on the bottom, then re-heapifying everything else above it… over and over again.
heapSort values cmp printfn "%A" values let tree = treeify values prettyPrint tree
Our output now shows a sorted array and binary heap tree:
[|5; 15; 31; 37; 44; 45; 53; 55; 56; 82|] |5 |-15 |--37 |---55 |---56 |--44 |---82 |-31 |--45 |--53
You can put a
printfn "%A" a statement in each iteration of those loops to visualize how this is working step-by-step, or even
prettyPrint (treeify a) to draw the tree at each iteration.
Don’t leave me now!
At this point the interviewer has probably gone home. That’s too bad for him, because we’re about to invert this binary heap by changing just one line:
let cmp<'a> x y = Comparer<'a>.Default.Compare(x, y) * -1 // ooooh!
cmp function and
heapSort will give you the inverse of your binary heap tree—if that’s even what the interviewer meant by inverting.
There’s another interpretation that says the desired solution is to simply swap the left and right nodes recursively, creating a mirror image of the tree. It seems like they would’ve said to reverse, mirror, or flip the tree instead, but whatever. Creating a mirrored tree would require just one function that recurses from the root node, swapping left and right nodes.
We can do that with a recursive fold function:
let invert tree = let rec fold tree acc = match tree with | Node(v, l, r) -> Node(v, fold r tree, fold l tree) | Nub -> tree fold tree Nub let inverted = invert tree prettyPrint inverted
invert kicks the
fold off with just a
Nub, pattern matches on
Nodes, and generates new
Nodes which call
fold recursively with the left and right children swapped.