If you're a web developer like me, you might know about tree data structures, but the need to write your own probably hasn't arisen. Like so many things we depend on as web developers, they are the shoulders of but one of many giants that we stand upon.
Trees make so much possible because they offer excellent trade-offs as a data structure: they give us fast lookup and insertion, and as a bonus, they're easy to write to and retrieve from permanent storage. Because they're such a practical data structure, you'll find that they power fundamental things we rely on, like databases.
But you probably don't need convincing that trees are useful. I wish my job gave me more excuses to work with them! The funny thing, though, is that interviewers seem to like asking about them, even if you never end up touching them on the job!
JavaScript Tree Class
First things first, let's look at an implementation of a tree class in JavaScript.
class Tree {
constructor(data, left = null, right = null) {
this.data = data;
this.left = left;
this.right = right;
}
insert(tree) {
if (tree.data >= this.data) {
this.insertRight(tree);
} else {
this.insertLeft(tree);
}
}
insertLeft(tree) {
if (this.left) {
this.left.insert(tree)
} else {
this.left = tree;
}
}
insertRight(tree) {
if (this.right) {
this.right.insert(tree)
} else {
this.right = tree;
}
}
}
t = new Tree("b");
t.insert(new Tree("a"));
t.insert(new Tree("c"));
t.insert(new Tree("d"));
console.log(t);
The Tree class itself accepts other instances of Tree as its children, making it a recursive data structure. The insertLeft and insertRight methods are helpers that exist to make the main insert method a little more readable.
With this basic implementation in place, let's take a look at some common interview questions that might pop up.
Building trees from arrays
The first challenge we'll take a look at will actually double as a useful tool when working with the rest of the problems. If we're going to implement algorithms to work with trees, we'll need a way to accept sample data to test the code.
We'll build our trees from arrays that store nodes in what's known as level order. This just means that all of the nodes for a given level of the tree will be adjacent in the input array. This will make more sense if we take an example:
[1, 2, 3, 4, 5, 6, 7]
This input array would correspond to the following tree:
How can we turn this array into the tree above, given the tree class we defined earlier?
The first thing to notice about the input array is the pattern that it follows:
- The left child of the node at i will be i * 2 + 1
- The right child of the node at i will be i * 2 + 2
Let's write a buildTree function step by step.
If we used a for loop to build tree nodes, it might look something like the following.
function buildTree(items) {
let root = new Tree(items[0]);
for (let i = 1; i < items.length; i++) {
let node = new Tree(items[i]);
}
return root;
}
Although this would produce tree nodes for each our array items, there's a pretty big problem here. None of the nodes have their left or right children populated.
Every node we encounter can be a parent, but unless it's the first item, we don't immediately set its left or right children. We can see, however, that the first node we encounter will be the first node to have children assigned.
You could say we assign children to nodes on a first in, first out basis. That sounds like a pretty good job for a queue. Adding an item to a queue places it at the end, while popping from a queue removes an item from the beginning (like a line at the supermarket). We'll put each node on the queue and we'll pop once a node has both children assigned.
function buildTree(items) {
let root = new Tree(items.shift());
let q = [root];
for (let i = 0; i < items.length; i++) {
let node = new Tree(items[i]);
if (q[0].left === null) {
q[0].left = node;
} else {
q[0].right = node;
q.shift(); // Remove node from beginning
}
q.push(node);
}
return root;
}
This version of buildTree is almost what we need, but it's missing a few features. I wanted to show this version first because it captures the essence of the idea.
If you recall the tree diagram at the beginning, you might have noticed that every node had two children, with the exception of the leaf nodes (the nodes at the last level or bottom). This kind of tree is referred to as a full tree. Our current buildTree function only works with full trees at the moment.
We can represent missing nodes as nulls in the input array.
[1, 2, 3, 4, null, 6, 7]
Let's also assume that buildTree can accept an empty array, in which case it should return null instead of a tree node.
With these extra requirements, our function will look like this:
function buildTree(items) {
let root = null;
let q = [];
let count = 0;
for (let i = 0; i < items.length; i++) {
let node = items[i] !== null ? new Tree(items[i]) : null;
if (!root) {
root = node;
} else {
if (!count) {
q[0].left = node;
count++;
} else {
q[0].right = node;
count = 0;
q.shift();
}
}
if (node)
q.push(node);
}
return root;
}
Notice that instead of checking for null, we use a count variable to determine whether or not we're done with the node at the front of the queue. This is because null can be a legitimate value in the array, so we can't check for that to see if a child has yet to be assigned.
Now we're ready to solve a few problems! I'll present problems roughly in order of increasing difficulty.
Maximum depth
Let's say you're given a tree and asked to determine its maximum depth. Here's an example tree we can work with for this problem.
This is a pretty simple tree, but it illustrates the problem. I've labeled each node with its own depth. In this example, the answer we want to return is 3.
The key to recursion is breaking the problem down into its simplest form.
- When would recursion stop, or in other words, what is the base case?
- What is the question we're asking at each step?
In this problem, recursion stops when we reach a node that has no children. At each step, we ask whether the left or right sub-tree is deeper, and return the max depth of the two.
function maxDepth(root) {
if (!root) {
return 0; // No children, recursion stops.
}
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
console.log(maxDepth(buildTree([1, 2, 2, null, null, 3, null])));
Invert tree
Here we're asked to invert a tree so that the left tree in the example above is mirrored to look like the tree on the right.
I think it's easiest to understand the solution if you imagine a tree with only a root and two children.
Starting with the root, we would call invertTree on the left node, which would in turn call invertTree once more before returning itself. The same would happen with the right node. We can then consider everything beneath the root to have been swapped. All that's left to do at that point is swap child references.
function invertTree(root) {
if (!root) {
return null;
}
let left = invertTree(root.left);
let right = invertTree(root.right);
root.left = right;
root.right = left;
return root;
}
console.log(invertTree(buildTree([1, 2, 3, 4, 5, 6, 7])));
Bottom left-most node
In this problem we're trying to find the bottom left-most node of the tree and return the value of that node. The key to understanding this problem for me involved rephrasing the challenge: find the first node of the last row of the tree.
It will be difficult to know whether a node is in the last row, or if it is the first node in a row, if we solve this problem recursively. An easier solution would be to use a breadth-first search of the tree. Breadth-first search traverses the tree in level order, which is exactly what we need.
In the example above we want our function to return 6. Let's take a look at the code.
function bottomLeft(root) {
let nodes = [root, null];
firstNode = null;
while (nodes.length) {
let node = nodes.shift();
if (nodes.length && node === null) {
nodes.push(null); // End of tree row, insert null to mark new row
firstNode = null;
} else if (node) {
if (!firstNode) {
firstNode = node; // Encountered first node of current row
}
if (node.left) {
nodes.push(node.left);
}
if (node.right) {
nodes.push(node.right);
}
}
}
return firstNode.data;
}
console.log(bottomLeft(buildTree([1, 2, 3, null, null, 6, 7])));
This is a fairly standard breadth-first search, but there are a few extra quirks specific to solving this problem.
Null values in the queue are used to determine where one row of the tree begins and another ends. This is important because the firstNode variable keeps track of the first node in each row, and we wouldn't know when to reset firstNode without some kind of separator value.
We don't actually need to track the depth of the tree. Because this is a level order traversal, firstNode will be the first node of the last row once the queue is exhausted.
Wrapping up
I hope you've enjoyed this intro to binary tree problems! Let me know if you have questions or feedback. I'd like to write up some more problems and their solutions when I have the opportunity.
Oldest comments (0)