Coding Interview Question: Find Width of a Tree
This is the second article in the series about tree-related coding interview questions. In the previous article, we took a look at how to traverse a binary and a non-binary tree in a breadth-first manner. However, only traversing a tree is not very useful. In an interview setting, you would most likely be asked to go through a tree and do some kind of manipulation on the nodes or get some information about them. A potential interview question could be related to finding the width of the tree.
The Problem
Given the root of a tree, return an array with the length of each level.
Given this tree, we would have to return an array [1, 3, 3, 2].
Before we even start solving the problem, we need to figure out whether to use breadth-first or depth-first traversal. The answer should be clear just by looking at the tree: since we need to calculate the width of the tree, we should traverse it in a breadth-first manner. If we were asked for the length of it, we would reach out for the depth-first method.
The solution
Now we can get down to business! We’re given a root node, with information about its data and an array of its children. We need to go through the whole tree and make sure that we note down when the level changes.
We will reuse the traversal function that we have previously discussed in the Breadth-First Tree Traversal, Explained Simply (For Binary and Non-Binary Trees) article.
const traverseTree = () => { const toBeTraversedArray = [root]; const traversedTree = []; while (toBeTraversedArray.length > 0) {
let currentNode = toBeTraversedArray.shift();
traversedTree.push(currentNode); if (currentNode.children.length > 0) {
toBeTraversedArray.push(...currentNode.children);
} }
return traversedTree;
}
With this function, we have more than half of the work done, as we are already traversing the whole tree and printing its nodes out in order of importance. However, it doesn’t quite solve the problem at hand, as we don’t know where one level ends and the other begins. To solve it, we need to do some modifications to our traverseTree function.
First, we need to make sure that every time we push children to the toBeTraversedArray, we “remember” that we have moved down by one level. One way to do it is by inserting some kind of a separator after we have pushed all the children of the current node to the toBeTraversedArray. This separator can be anything, as long as it’s not a node. I will be using a string x.
Before we do anything else, we check if the root element is passed to the function. If not, we just return an array with 0.
If the root element exists, we initiate the toBeTraversedArray with the root element and an x, indicating that there is only one element in the first loop.
We also need to keep count of the number of elements we have already traversed. And since we want to return all the counters in an array, we need an array for the counters as well.
I prefer to have a counter variable, which I increment on every loop and then push to the counterArray.
function getTreeWidth(root) {
const toBeTraversedArray = [root, 'x'];
let currentCounter = 0;
const counterArray = [];
}We have to make sure that we push the separator to the end of the toBeTraversedArray because this will be the condition of our while loop. If there is only one element left in the array, it means it’s the separator and we have to escape the loop.
function getTreeWidth(root) {
if (!root) return [0]; const toBeTraversedArray = [root, 'x'];
let currentCounter = 0;
const counterArray = []; while (toBeTraversedArray.length > 1) { const currentNode = toBeTraversedArray.shift(); if (currentNode === 'x') {
counterArray.push(currentCounter);
currentCounter = 0;
toBeTraversedArray.push('x');
} else {
currentCounter++;
toBeTraversedArray.push(...currentNode.children);
}
}
}
In the loop itself, we get the first element of the toBeTraversedArrayand check if it’s the separator. If so, it means that we have reached the end of a level. We push our currentCounter to the counterArray, reset the currentCounter and push the separator back to the toBeTraversedArray.
If the element at hand is a node, we just add its children to the toBeTraversedArray so we can come back to them later and then we increment the currentCounter.
When traversal is done, we have to make sure to push the last counter to the counterArray before we return it.
And that’s it. Let’s check if our function works as expected.
class Node {
constructor(data) {
this.data = data;
this.children = [];
}
}const root = new Node('CEO');
const CTO = new Node('CTO');
const CMO = new Node('CMO');
const COO = new Node('COO');const SeniorPM = new Node('Senior PM');
SeniorPM.children = [new Node('PM'), new Node('PM')];CTO.children = [new Node('Director of Infra'), new Node('Director of Eng')]CMO.children = [SeniorPM];root.children = [CTO, CMO, COO];console.log(traverseTree(root));
We get:
This solution is not the only correct answer to this question, it’s just the one that makes the most sense to me.
If you have suggestions for improvement or would like to share another solution, feel free to leave a comment. Let’s learn from each other. 🙂
Follow me so you don’t miss the upcoming coding challenges, explained simply!
Build composable applications
Don’t build web monoliths. Use Bit to create and compose decoupled software components — in your favorite frameworks like React or Node. Build scalable and modular applications with a powerful and enjoyable dev experience.
Bring your team to Bit Cloud to host and collaborate on components together, and greatly speed up, scale, and standardize development as a team. Start with composable frontends like a Design System or Micro Frontends, or explore the composable backend. Give it a try →
