The tree data structure is one of the most important and, at the same time, most feared data structures for coding interviews at product-based companies like Amazon, Google, Walmart, and Microsoft. Its extensive applications in software development justify the importance of tree data structure.
For example, the autocomplete feature in text editors is possible due to tree data structure. Whenever we search for something on Google we get results within a fraction of a second, this is possible due to tree data structure!
But as a beginner, it is complicated to decide where to begin and what to study. There are so many types of trees like AVL, Binary Tree, B-tree, N-tree Red-Black Tree, and many more that it may be impossible to study all these types.
But what if I tell you that there is another smarter way to master the tree data structures that will give you maximum output in minimum efforts?
Upon extensive research and analysis of all the previous questions asked in the interviews, Parikh Jain, the Founding Member of Coding Ninjas discusses “How to Master Tree Data Structures”.
In this article, we will discuss everything from scratch to master tree data structures, its prerequisites, and the pattern of problems generally asked in interviews.
What is a Tree?
A tree is a non-linear data structure that stores data in a hierarchical way instead of storing it in a linear fashion.
Some basic terminologies related to tree are:
- Node: The node is a structure that contains the value and is connected to other nodes going down.
- Root: The first node of the tree.
- Edges: The connecting link between two nodes.
- Parent node: The node which is the predecessor of any node.
- Child nodes: The node which is a descendant of any node
Now we know the basic terminologies of trees, so now we can frame the above definition in more technical terms. A tree can be defined as the collection of nodes, and these nodes are connected by edges. Each node contains a value and may have child nodes.
Image Source: Studytonight
From the above picture, we can observe that the tree’s structure has a very striking resemblance to the Christmas tree. Maybe that’s the reason it is called a tree!
Before we start learning the tree data structure, we need to understand some basic concepts that are building blocks in our journey to learn the tree.
Prerequisites for tree data structure are
Make sure you checkmark all the prerequisites before having a deep dive into the tree data structure. As mentioned earlier, we will give you the “Secret way” and a more thoughtful way to practice and learn tree data structure. Most product-based companies ask questions mainly on two types of tree: Binary Tree (BT) and Binary Search Tree (BST).
These two types cover almost 90% of the questions on trees asked in interviews. Having in-depth knowledge of these two trees is very important. We will discuss these trees and essential questions for both trees.
We will also look at some other types of trees with a curated list of questions to make you interview-ready and crack your dream job.
Binary Tree (BT or bt)
A binary tree is a special type of tree in which each node has at most two children. Each node has at most two children called left and right child.
A Binary Tree node contains the following parts:
- Pointer to the left child
- Pointer to the right child
Image Source: techiedelight
We will divide the question based on types ranging from basic to more advanced questions. The binary tree is very important for coding rounds. Even its basic questions like taking input in a binary tree are also very frequently asked in interviews.
Questions on Binary Tree traversal: Binary tree traversal is a very important and interesting topic. There are several different ways to traverse a binary tree, and questions on these traversals are very important. Following is a list of frequently asked binary tree traversals questions
- Pre-order Traversal
- Post-order Traversal
- In-order Traversal
- Level-order Traversal
- Boundary traversal– a very interesting and frequently asked question in the interviews.
- ZigZag traversal– a tricky and common question in interviews.
The construction of binary tree from preorder and inorder traversal is also an important question.
Basic questions: The basic questions are always important ones. If you know how to solve the basic question, you can solve the maximum question asked in interviews as most questions asked are variations of these questions. Following is a list of important basic questions on Binary Tree
Once you have implemented the basic question, another tree construction problem that you should try is Binary tree from the parent array.
Problems on Tree View: Most tricky and difficult yet very important questions on the binary tree are based on views of the tree. Views of the tree simply mean that you have to print the value of nodes of the tree in the order as they are visible when viewed from the given position. Following is a list of questions based on the tree view.
Above mentioned questions are crucial for interviews at product-based companies. Try to implement the question on your own to test out your preparation for interviews.
Binary Search Tree (BST or bst)
A binary search tree is a special type of binary tree which has the following properties.
- The left subtree of a node contains nodes with values less than the node’s value.
- The right subtree of a node contains nodes with values greater than or equal to the node’s value.
- The left and right subtree should also be binary search trees.
Image Source: Medium.com
Being a special type of binary tree, the question based on its properties is essential. Before implementing the complex operation, you should implement the basic insert delete and search operation on a binary search tree.
Construction of a:
are very important for your basic understanding of how the elements are placed in a BST.
Conversion Based Problem: Question on converting a given data structure to BST and BST to other data structures is commonly asked.
Try to implement the following questions.
Merging two BST is another frequently asked question in product-based companies.
If you want to practice more BST and Binary Tree questions, you can find them on CodeStudio.
It is a great platform developed by aspiring enthusiasts and working professionals who have experience in companies like Google, Amazon, Microsoft. At CodeStudio, you get interview problems, interview experiences, and practice problems that can help you to land your dream job.
Till now, we talked about Tree with a detailed practice path to learn BST and Binary Tree. But as told earlier, there are many other variations of trees. You should have a basic understanding of some of these variations as you may get some questions on basic operations on these variations. Some important types and Questions of trees that you should know about are as follows.
Generic or n-ary tree
N-ary tree can have n number of children for a given node, which makes it a little complex compared to BST and binary tree.
Image Source: Studytonight
You should try to implement basic operations like taking input and calculating the height of the tree.
Range query-based questions
Range query-based problems are very common in competitive programming.
In these questions, you asked to find something in a range like a sum. In such kinds of questions, Fenwick and Segment tree are very useful. These trees can efficiently update elements and perform operations. You should have a basic understanding of range-based problems. These problems are generally asked in competitive programming.
We have covered all important topics for the interview that are generally asked. But you may be asked for basic terminologies and properties of trees like B-tree, AVL tree, and Red-Black tree. Readout about these trees and have a basic understanding of these trees.
Frequently Asked Question
The tree is one of the most important data structures for interviews. While learning trees always start from basics, get a strong grip on basics first and then move to advanced topics try to implement the questions provided in this article.
The tree can be represented as a collection of nodes where each node is a data structure consisting of a value, together with a list of references to nodes.
We can’t say which one is best or worst. It depends on the use case of the problem.
The files in a storage (hard drive or ssd) are arranged as a tree with the root directory as the root of the tree.
Binary Search Tree(bst) is a binary tree with the nodes or keys arranged in an organized manner. With respect to the root, all the keys(could be a numeric value or any other type of data) in the left subtree are smaller than the root whereas, the keys in the right subtree are greater than the root. The idea of arranging the keys in this fashion is followed further to the left and right subtrees.
According to the use case, duplicate elements can either be placed in the left or right subtree but once decided, rule should strictly follow through the lower levels of the tree. Almost every 3D game uses BST to figure out which object to render next.
In this article, we discussed the tree data structures in-depth from the viewpoint of technical interviews at product-based companies. We discussed the Binary search tree and binary tree in detail with a curated list of questions to crack interviews and discussed some important topics to master tree data structures.
By Pranchal Agrahari