Interview Kickstart has enabled over 3500 engineers to uplevel.
Trees are all around us. What does a typical tree look like? It has leaves, big branches, small branches, and under the ground, it has roots. Depending on the type of habitat of the tree, it can be very large and dense.
Inspired by a natural tree, trees in the data structure look pretty similar. They are also made of roots, branches, leaves and also can be very large and dense. However, there is one difference — trees in data structures have their roots on the top and the leaves below. They are upside-down trees.
For any software engineer or developer preparing for a tech interview, brushing up on data structures and algorithm concepts is a must. Many of the problems asked at FAANG and top tech companies are based on these basic but key concepts. Tree is one such topic you must review — and this article will help you with just that. Here’s what we’ll cover:
Unlike linear data structures (linked list, stack, queue), a tree is a hierarchical, non-linear data structure composed of one or more nodes (or no node at all). One node of a tree is directly or indirectly connected to every other node without forming a cycle. Three nodes A, B, C will form a cycle if node A is connected to node B and node B is connected to C, and also node C is again connected to node A.
A node is a structure that may contain a value or a condition or a separate data structure like an array, linked list, or even a tree. Each node of the tree can have zero or more child nodes, but each child node will have only one parent node (except the root node, which has no parent). There can be multiple ancestors to a node (like a parent, grandparent, and so on).
Now you know what a tree is. Let’s look at an example of how you can use it.
Suppose you are given a task to implement a file management system. What data structure will be the best fit to solve this problem?
What assumptions can we make about this file management system?
Considering all these cases, we know that an array, stack, or queue will not work. Can we implement this with the help of a linked list? We could make a linked list in such a way that if there is a directory at any particular node, we create a new linked list from here. What will this look like?
It looks similar to a tree, right? So, we tried to use a linked list but ended up using a tree because the problem can easily be solved using tree data structure — each internal node of the tree will be a directory, and each leaf node will be a file. We can implement a hierarchical data structure as follows:
We’ve already spoken about some of these; let’s look at each of them in detail.
A node is a structure that may contain a value or a condition or a separate data structure like an array, linked list, or even a tree. Each node of the tree can have zero or more children, but it can have only one parent, and if the node is a root node, it will not have any parent.
// Structure of binary tree node in C
struct node {
struct node* left;
struct node* right;
int data;
};
A root is the first node of the tree, or we can say the node that does not have any parent. If the root node is connected to any other node, then that node is called the immediate child of the root node.
Each node with a parent and a child is called the inner node or internal node of the tree.
Nodes that do not have any further child nodes are called leaf nodes of the tree. A root node that does not have any children can also be called the only leaf node of the tree.
Each node of a tree forms a recursive subtree of the tree. A subtree of a tree consists of a node n and all of the descendants of node n.
Two nodes in a tree that are connected through a link are called the edge of the tree. In a tree with n number of nodes, there will be (n - 1) edges. Also, two siblings in a tree cannot be connected through an edge; otherwise, they will form a cycle, which violates the property of the tree.
In a tree, two or more nodes that share the same parent node are called sibling nodes.
Level of the tree indicates how far you have gone from the root node. The level of the tree starts with 0 and increments by one as you are going from top to bottom.
The tree’s height is the total number of edges from the root node to the farthest leaf node of the tree.
The depth of the tree is similar to the height; the only difference is that it goes backward. It means the depth of the node is the total number of edges from the root node to the current node. It is very similar to the level of the node.
In data structures, there are various types of trees. The selection of trees depends upon the nature of the problems we are trying to solve. These are the basic types of trees:
A binary tree is a tree in which every internal node and root node has at most two children. These two child nodes are often called the left child node or right child node of the node.
A binary search tree is a binary tree that has the following properties:
Full form of AVL is Adelson-Velsky and Landis. AVL tree is the self-balancing binary search tree with the property that the difference between the height of the left and right subtree of the tree should not be more than one for any node of the tree.
If you implement a tree, you need a way to perform certain operations like finding the node’s depth, height of the node, order each node of the tree (from left to right), etc.
All these operations can be performed easily with the help of tree traversal algorithms.
There are basically three ways of traversing a binary tree:
These traversal techniques are not only limited to the binary tree; they can easily be modified for an n-ary tree (a tree with a maximum of n children).
In inorder traversal of the binary tree, we traverse the left subtree of the tree first and then root node, and then the right subtree of the tree.
void inorder(struct node* root) {
if(root == NULL) {
return;
}
inorder(root -> left);
cout << root -> data << " ";
inorder(root -> right);
}
In preorder traversal, we traverse the root node first, then the left subtree of the binary tree, and finally, the node’s right subtree.
void preorder(struct node* root) {
if(root == NULL) {
return;
}
cout << root -> data << " ";
preorder(root -> left);
preorder(root -> right);
}
In postorder traversal, we traverse the left subtree of the node and then the right subtree tree of the node, and finally, the root node of the tree.
void postorder(struct node* root) {
if(root == NULL) {
return;
}
postorder(root -> left);
postorder(root -> right);
cout << root -> data << " ";
}
Check out the Tree Traversal article to learn more.
A tree is implemented with the help of pointers. The pointers are responsible for connecting one node of the tree to another. The basic structure of the node of a binary tree has one pointer pointing to the left child of the node, another pointer pointing to the right node of the tree, and a variable storing the value of the node.
Here is the basic implementation of the binary tree with the help of two pointers left and right
#include <bits/stdc++.h>
using namespace std;
// Structure of the node
struct node {
int data;
struct node* left; // left child of the node
struct node* right; // right child of the node
};
struct node* make_node(int value) {
// Function used to create a node
struct node* new_node = new struct node;
new_node -> data = value;
new_node -> left = NULL;
new_node -> right = NULL;
return new_node;
}
void inorder_traversal(struct node * root) {
if(root == NULL) {
return;
}
inorder_traversal(root -> left);
cout << root -> data << " ";
inorder_traversal(root -> right);
}
int main() {
struct node* root = NULL;
root = make_node(1);
root -> left = make_node(2);
root -> right = make_node(3);
root -> left -> left = make_node(4);
root -> right -> right = make_node(5);
inorder_traversal(root);
return 0;
}
Question 1: Find the depth of a given node in a binary tree? If no node is present, print -1.
#include <bits/stdc++.h>
using namespace std;
// Structure of the node
struct node {
int data;
struct node* left;
struct node* right;
};
struct node* make_node(int value) {
// Function used to create a node
struct node* new_node = new struct node;
new_node -> data = value;
new_node -> left = NULL;
new_node -> right = NULL;
return new_node;
}
int find_depth(struct node* root, int value) {
// Return depth of the node if the node exist otherwise, it will return -1
if(root == NULL) {
return -1;
}
int ans = -1;
stack < pair < struct node*, int > > st;
st.push({root, 0});
while(!st.empty()) {
pair < struct node*, int > node_obj = st.top();
st.pop();
struct node* temp = node_obj.first;
int depth = node_obj.second;
if(temp -> data == value) {
ans = depth;
break;
}
if(temp -> left != NULL) {
st.push({temp -> left, depth + 1});
}
if(temp -> right) {
st.push({temp -> right, depth + 1});
}
}
return ans;
}
int main() {
struct node* root = NULL;
root = make_node(1);
root -> left = make_node(2);
root -> right = make_node(3);
root -> left -> left = make_node(4);
root -> right -> right = make_node(5);
cout << "Depth of node 4 is " << find_depth(root, 4) << "\n";
cout << "Depth of node 1 is " << find_depth(root, 1) << "\n";
cout << "Depth of node 3 is " << find_depth(root, 3) << "\n";
cout << "Depth of node 10 is " << find_depth(root, 10) << "\n";
return 0;
}
Question 2: Print Level order traversal of binary tree
#include <bits/stdc++.h>
using namespace std;
// Structure of the node
struct node {
int data;
struct node* left;
struct node* right;
};
struct node* make_node(int value) {
// Function used to create a node
struct node* new_node = new struct node;
new_node -> data = value;
new_node -> left = NULL;
new_node -> right = NULL;
return new_node;
}
void print_level_order_traversal(struct node* root) {
queue < struct node* > q;
q.push(root);
while(!q.empty()) {
struct node* temp = q.front();
q.pop();
cout << temp -> data << " ";
if(temp -> left) {
q.push(temp -> left);
}
if(temp -> right) {
q.push(temp -> right);
}
}
}
int main() {
struct node* root = NULL;
root = make_node(1);
root -> left = make_node(2);
root -> right = make_node(3);
root -> left -> left = make_node(4);
root -> right -> right = make_node(5);
print_level_order_traversal(root);
return 0;
}
Here are a few more questions for you to practice:
Question 1: Can a binary tree be converted into a binary search tree?
Answer Yes, a binary tree can be converted into a binary search tree by following the properties of a binary search tree while performing the insert operation.
Question 2: How do you find if two binary trees are identical?
Answer: Two binary trees are considered the same if they are structurally identical and the nodes have the same value. So all we need to do is to check this condition recursively:
Nailing tech interviews at FAANG and Tier-1 tech companies can be challenging even for seasoned software engineers. It requires a deep understanding of data structure and algorithms as well as systems design.
If you’re looking for guidance and help to nail these questions and more, sign up for our free webinar. As pioneers in the field of technical interview prep, we have trained thousands of software engineers to crack the toughest coding interviews and land jobs at their dream companies, such as Google, Facebook, Apple, Netflix, Amazon, and more!
----------
Article contributed by Problem Setters Official