This content originally appeared on Bits and Pieces - Medium and was authored by Lina Suodyte
For Binary and Non-Binary Trees
Even though the Internet is full of sample interview questions and tips and tricks on how to solve them, more often than not, I find these explanations quite complicated and discouraging. This is why I’ve decided to solve some of the interview questions myself and try to explain them in the simplest, most understandable language possible. The code examples are given in JavaScript but I explain every step in plain English so it shouldn’t be hard to write the solution in any programming language.
This time we’re going to traverse a tree. But before we do, let’s quickly recap some terms.
A tree is a nonlinear data structure (as opposed to arrays, linked lists, stacks, and queues). It usually has a root node and children nodes, which, in return can have their children nodes. A tree can be binary on non-binary. In a binary tree, each node has at most two — left and right — children. A node in a non-binary tree can have more children.
Traversing a tree means going through every node in it. The two most common ways to traverse a tree are breadth-first and depth-first. Breadth-first traversal means that we start from the top node, then go one level down, go through all of the children nodes from left to right. When there are no children left, we go one level down and repeat the process until we have visited every level. We can imagine this as a queue: we start from the top and finish at the bottom.
In a depth-first traversal, we start from the top node, go down to its immediate children, then down its children and down and down we go until we reach the last child node. When we hit the bottom, we move up and do the same on the other side.
However, in this article, we will explore the breadth-first traversal of binary and non-binary trees.
First, let’s take a look at our binary tree. The following example is common in many job interviews.
The Problem
We have a tree that shows the hierarchical structure of a company, with the CEO on top, the CTO and the CMO as their direct reports, and so on. Print out a list of positions in order of their importance.
The Solution
We can immediately see that we’re dealing with a binary tree, as no node has more than two children.
In order to create a tree, we first need a class for a single Node.
class Node {
constructor(data) {
this.data = data;
this.left = null;
this.right = null;
}
}Because our tree is binary, each node will store information about its own data and about its left and right children. When we initialise a node, it has no children, unless we explicitly add them. Now, let’s create our tree:
const root = new Node('CEO');
root.left = new Node('CTO');
root.right = new Node('CMO');
root.left.right = new Node('Director of Engineering');
root.left.left = new Node('Director of Infra');
root.right.left = new Node('Product Manager');Now that our tree is ready, let’s write the actual function that traverses it.
We will start at the top of the tree, we will check every node in it (in this case, it’s only one because the first level contains only the root), then move one level down, check all the nodes there and so on until we reach the last level.
In order to keep track of the nodes that need to be checked, we will initiate an array. Because we start from the most top level and there is only the root node to be checked, we add it to the array right away.
const printTree = () => {
let toBeTraversedArray = [];
array.push(root);
}In order to search the rest of the tree, we need to get every element from our array and check them one by one, getting them from the beginning of the array. If the current element has children, we enqueue them in the same array (or, in other words, push them to the end of it) so we can come back to them later. And since we need to perform the same operation on all elements of the toBeTraversedArray array, we can use a while loop.
In the loop, we take the first element in the array and check if it has a left child. If so, we push it to the toBeTraversedArray. Then we check if the node has a right child and perform the same operation.
const traverseTree = () => {
const toBeTraversedArray = [];
toBeTraversedArray.push(root);const traversedTree = [];
while (toBeTraversedArray.length > 0) {
let currentNode = toBeTraversedArray.shift();
traversedTree.push(currentNode); if (currentNode.left != null) {
toBeTraversedArray.push(currentNode.left);
} if (currentNode.right != null) {
toBeTraversedArray.push(currentNode.right);
}
}return traversedTree;
}
console.log(traverseTree());
Once this loop is done, we get the next element in the toBeTraversedArray array, which in this case would be the first left child of the root node and we go through the same process again. That’s it! We traversed a binary tree.
But what if a node of a tree has more than two children?
Now we have the CTO, the CMO and the COO all reporting to the CEO.
In that case, instead of keeping record of left and right children separately, we can save all the children in an array:
class Node {
constructor(data) {
this.data = data;
this.children = [];
}
}We can then add children from left to right:
const root = new Node('CEO');
root.children = [new Node('CTO'), new Node('CMO'), new Node('COO')];In this case, our check for the left and the right node in traverseTree function doesn’t make sense anymore. Instead, we can check if there are any children in the children array and if so, push them to toBeTraversedArray array one by one:
const traverseTree = () => {
const toBeTraversedArray= [root];
toBeTraversedArray.push(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;
}
console.log(traverseTree());
And that’s it!
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 →
Learn More
- How We Build Micro Frontends
- How we Build a Component Design System
- The Composable Enterprise: A Guide
- 7 Tools for Faster Frontend Development in 2022
Programming Interview Question: Explain Breadth-First Tree Traversal was originally published in Bits and Pieces on Medium, where people are continuing the conversation by highlighting and responding to this story.
This content originally appeared on Bits and Pieces - Medium and was authored by Lina Suodyte
Lina Suodyte | Sciencx (2022-03-21T11:19:47+00:00) Programming Interview Question: Explain Breadth-First Tree Traversal. Retrieved from https://www.scien.cx/2022/03/21/programming-interview-question-explain-breadth-first-tree-traversal/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.