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: 

• What Are Trees in Data Structure?
• Using the Tree Data Structure
• Types of Trees
• Tree Traversal
• Application of Tree Data Structure
• Advantages of the Tree Data Structure
• Implementation of the Tree Data Structure
• Examples of Tech Interview Problems and Questions on Tree Data Structure
• FAQs on Tree Data Structure

What Are Trees in Data Structure?

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.

Using the Tree Data Structure

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?

• It could have multiple directories or folders.
• Each directory could also have multiple directories inside it.
• There may be a case where a user has stored a file and a directory in the same folder side by side.
• There can also be cases where there are no files in a directory.
• There can be multiple types of files like jpg, txt, mp3, mp4, etc.
  

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: 

Terminology Related to Tree

We’ve already spoken about some of these; let’s look at each of them in detail.

1. Node

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;
};

2. Root Node

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.

3. Internal Nodes or Inner Node

Each node with a parent and a child is called the inner node or internal node of the tree.

4. Leaf Node

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.

5. Subtree of 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.

6. Edge

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.

7. Siblings

In a tree, two or more nodes that share the same parent node are called sibling nodes.

8. Level of the Tree

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.

9. Height of the tree

The tree’s height is the total number of edges from the root node to the farthest leaf node of the tree.

10. Depth 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.

Types of Trees

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: 

1. Binary Tree
2. Binary Search Tree
3. AVL Tree
4. B-tree

1. Binary Tree

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.

2. Binary Search Tree

A binary search tree is a binary tree that has the following properties: 

• The left subtree of the node only contains values less than the value of the node.
• The right subtree of the node only contains values greater than or equal to the value of the node.
• The left and right subtree of the nodes should also be the binary search tree.

3. AVL Tree

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. 

4. B-tree

• A B-tree is a variation of an m-way tree. An M-way tree is a multi-way tree similar to a binary tree. In an m-way tree of order m, each node of the tree can store at most m-1 values, and it can have at most m children.
• A B-tree of order n can have at most (n - 1) keys and n children.
• B-tree can store a large number of keys in a single node. This way, the height of the tree can be minimized.
• In a B-tree, all the leaf nodes are at the same level because insertion in B-tree occurs at the leaf node, and if the particular node of order n has more than n children, then that node gets split from the middle by creating a new node with its two-child node.

• In a B-tree, the root node must have at least two child nodes because of the splitting nature of the node if the overflow of keys occurs. 
  

Tree Traversal

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: 

1. Inorder Traversal
2. Preorder Traversal
3. Postorder Traversal

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).

Inorder Traversal (Left, Root, Right)

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);
}

Preorder Traversal (Root, Left, 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);
}

Postorder Traversal (Left, Right, Root)

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.

Application of Tree Data Structure

• Trees are very useful in solving problems in which there is a hierarchical relation between the values you are given, like our file management system.
• Every browser uses a tree data structure to parse document elements or DOM elements of the web page.
• If the data is organized in the form of a binary search tree, then we can search any element in the tree in O(log(n)) time in the average case (but can go up to O(n) in the worst case). And if we use a self-balancing binary search tree like AVL tree, then the worst-case time complexity will be guaranteed to be O(log(n))
• Tree forms the backbone of other complex data structures like heap, priority queue, spanning tree, etc.
• Trees are also used for decision-making algorithms (for example, decision trees).
• B-tree has its own application in storage systems like databases and file management because they can store multiple keys on one node.
• Trees are also used in compilers for checking the accuracy of programs.
• Trees are also very widely used in the domain name server. 
  

Advantages of the Tree Data Structure

• With the help of a self-balancing binary search tree, search operation in the tree can be reduced to O(log(n)) time complexity.
• Trees provide a hierarchical way of representing and storing the data, which is very helpful in storage systems like file management and databases.
• A tree is a flexible data structure — one subtree of a node can be removed easily, and also it can be attached to any other node without much effort.
• Different traversals of trees arrange nodes in a different order, which can be helpful in different contexts depending upon the problem.

Implementation of the Tree Data Structure

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;
}

Examples of Tech Interview Problems and Questions on Tree Data Structures

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: Find the diameter of the binary tree
• ‍Question 2: Count good nodes in a binary tree
• ‍Question 3: Invert binary tree
• ‍Question 4: Search in a binary search tree
• ‍Question 5: Create a balanced binary tree
• ‍Question 6: Find the maximum depth of the binary tree
• ‍Question 7: Boundary traversal of binary tree
• ‍Question 8: Diagonal traversal of binary tree
• ‍Question 9: Zig-Zag tree traversal
• ‍Question 10: XOR sum of the subtree of a given node
• ‍Question 11: LCA of binary tree
• ‍Question 12: Check if given binary tree is a subtree of another binary tree

FAQs on Tree Data Structure

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:

1. If both the trees are empty then they are identical so return true.
2. If the trees are nonempty, then check the following condition recursively:

1. Check the value of the root node of both trees; if they are not equal, then it means trees are not identical, so return false
2. If the value of the root node of both trees is identical, check if the left subtree and right subtrees are identical.
3. If any of the subtrees are not identical, return false else, return true.

Ready to Nail Your Next Coding Interview?

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!

Sign up now!

----------

Article contributed by Problem Setters Official