Top 32 Trees Interview Questions And Answers

Question 1

Define Tree Data Structure

Accepted Answer

**Trees** are well-known as a _non-linear_ data structure. They don’t store data in a linear way. They organize data _hierarchically_.

A **tree** is a collection of entities called **nodes**. Nodes are connected by **edges**. Each node contains a **value** or **data** or **key**, and it may or may not have a **child** node. The first node of the tree is called the **root**. **Leaves** are the last nodes on a tree. They are nodes without children.

![](https://miro.medium.com/max/975/1*PWJiwTxRdQy8A_Y0hAv5Eg.png)

Question 2

Define Binary Tree

Accepted Answer

A normal tree has no restrictions on the number of children each node can have. A **binary tree** is made of nodes, where each node contains a "left" pointer, a "right" pointer, and a data element.

There are three different types of binary trees:

* **Full binary tree**: Every node other than leaf nodes has 2 child nodes.
* **Complete binary tree**: All levels are filled except possibly the last one, and all nodes are filled in as far left as possible.
* **Perfect binary tree**: All nodes have two children and all leaves are at the same level.

![](https://study.com/cimages/multimages/16/0e0646ba-30e5-40d9-b45c-a138f038f05b_full_complete_perfect.png)

Question 3

What's the difference between the data structure Tree and Graph?

Accepted Answer

**Graph:**
* Consists of a set of vertices (or nodes) and a set of edges connecting some or all of them
* Any edge can connect any two vertices that aren't already connected by an identical edge (in the same direction, in the case of a directed graph)
* Doesn't have to be connected (the edges don't have to connect all vertices together): a single graph can consist of a few disconnected sets of vertices
* Could be directed or undirected (which would apply to all edges in the graph)

**Tree:**
* A type of graph (fit with in the category of Directed Acyclic Graphs (or a DAG))
* Vertices are more commonly called "nodes"
* Edges are directed and represent an "is child of" (or "is parent of") relationship
* Each node (except the root node) has exactly one parent (and zero or more children)
* Has exactly one "root" node (if the tree has at least one node), which is a node without a parent
* Has to be connected
* Is acyclic, meaning it has no cycles: "a cycle is a path [AKA sequence] of edges and vertices wherein a vertex is reachable from itself"
* Trees aren't a recursive data structure

![](https://miro.medium.com/max/2262/1*-yHATwTlY2hwceJ93-D-cw.jpeg)

Question 4

What is Binary Search Tree?

Accepted Answer

**Binary search tree** is a data structure that quickly allows to maintain a _sorted list_ of numbers.

* It is called a _binary tree_ because each tree node has maximum of two children.
* It is called a _search tree_ because it can be used to search for the presence of a number in `O(log n)` time.

The properties that separates a binary search tree from a regular binary tree are:

* All nodes of left subtree are less than root node
* All nodes of right subtree are more than root node
* Both subtrees of each node are also BSTs i.e. they have the above two properties

![](https://cdn.programiz.com/sites/tutorial2program/files/bst-vs-not-bst.jpg)

Question 5

How to implement a _Tree_ data-structure? Provide some code.

Accepted Answer

That is a basic (generic) tree structure that can be used for `String` or any other object:

Question 6

What is Height and Depth of a Tree and its Nodes?

Accepted Answer

* The **depth of a node** is the length of the _path to its root_ * The **height of a node** is the number of edges on the longest path from the node to a leaf * The **height of a tree** is the length of the _longest path to a leaf_
![](https://www.growingwiththeweb.com/images/data-structures/avl-tree/height-vs-depth.svg)

Question 7

Provide some practical examples of using Depth-First Search (DFS) vs Breadth-First Search (BFS)?

Accepted Answer

* **Depth-first searches** are often used in simulations of games (and game-like situations in the real world). In a typical game you can choose one of several possible actions. Only some paths in a game tree lead to your win. Some lead to a win by your opponent, when you reach such an ending, you must back up, or backtrack, to a previous node and try a different path. In this way you explore the tree until you find a path with a successful conclusion. Another example, given a family tree if one were looking for someone on the tree who’s still alive, then it would be safe to assume that person would be on the bottom of the tree. This means that a BFS would take a very long time to reach that last level. A DFS, however, would find the goal faster.

* The **breadth-first search** has an interesting property: It first finds all the vertices that are one edge away from the starting point, then all the vertices that are two edges away, and so on. This is useful if you’re trying to find the shortest path from the starting vertex to a given vertex. Breadth-first search can be used for finding the neighbour nodes in peer to peer networks like BitTorrent, GPS systems to find nearby locations, social networking sites to find people in the specified distance.

Question 8

Why do we want to use Binary Search Tree?

Accepted Answer

If we implement a **balanced binary search tree**, we can always keep the cost of `insert()`, `delete()`, `lookup()` to `O(log n)` where `n` is the number of nodes in the tree - so the benefit really is that lookups can be done in logarithmic time which matters a lot when n is large. This is much better than the _linear_ time `O(n)` required to find items by key in an (unsorted) array, but slower than the corresponding operations on hash tables.

Question 9

What are advantages and disadvantages of BST?

Accepted Answer

**Advantages of BST:**

* If we implement a balanced binary search tree, we can always keep the cost of `insert()`, `delete()`, `lookup()` to `O(log n)`
* BST is much faster than an array at search, insert, and delete (`O(log n)` vs `O(n)`)
* Code is simple relative to other data structures

**Disadvantages of BST:**

* BST is slightly slower than an array at access (`O(log n)` vs `O(1)`)
* A binary search tree can get out of balance (_imbalanced_) or become _degenerated_
* We should always implement a _balanced_ binary search tree (using some _self-balancing mechanism_) - AVL tree, Red-Black tree, Splay tree. Otherwise the cost of operations may not be logarithmic and degenerate into a linear search on an array.

Question 10

What is Balanced Tree and why is that important?

Accepted Answer

A tree is said to be balanced only when all three conditions satisfy:
* The left and right subtrees height differ by at most one
* The left subtree is balanced
* The right subtree is balanced

**Height-balancing** requirement:
* A node in a tree is height-balanced if the heights of its subtrees differ by no more than 1. 
* A tree is height-balanced if all of its nodes are height-balanced.

![](https://www.afternerd.com/blog/wp-content/uploads/2018/03/balanced.jpg)

In a balanced BST, the height of the tree is `log n` where `n` is the number of elements in the tree. In the worst case and in an unbalanced BST, the height of the tree can be upto `n` which makes it same as a linked list. In the worst case each of the operations (lookup, insertion and deletion) takes time `O(n)` that shall be avoided.

> Balanced BST maintains `h` = `O(log n)` so all operations run in `O(log n)` time.

Top 32 Trees Interview Questions

Define Tree Data Structure

Define Binary Tree

What is Height and Depth of a Tree and its Nodes?

What's the difference between the data structure Tree and Graph?

What is Binary Search Tree?

Classify Tree Traversal Algorithms. Provide some visual explanation.

What is Diameter of a Tree?

What is AVL Tree?

Explain the difference between Binary Tree and Binary Search Tree with an example?

What are advantages and disadvantages of BST?

What is Balanced Tree and why is that important?

Provide some practical examples of using Depth-First Search (DFS) vs Breadth-First Search (BFS)?

Why do we want to use Binary Search Tree?

What is the difference between Tree Depth and Height?

Why does a Breadth First Search (BFS) use more memory than Depth First Search (DFS)?

Explain how to balance AVL Tree?

Is there any reason anyone should use BSTs instead of AVLs in the first place?

How do we know whether we need to use BSF or DSF algorithm?

What is the difference between Heap and Red-Black Tree?

Explain what the main differences between red-black (RB) trees and AVL trees

Explain what is B-Tree?

How does inserting or deleting nodes affect a Red-Black tree?

What is the time complexity for insert into Red-Black Tree?

Explain a B-Tree data structure for 5 years old

What is Red-Black tree?

What's the main reason for choosing Red Black (RB) trees instead of AVL trees?

How is an AVL tree different from a B-tree?

Why is a Hash Table not used instead of a B-Tree in order to access data inside a database?

Why do we need a separate datastructure like B-Tree for database and file system?

How are B-Trees used in practice?

What are the differences between B trees and B+ trees?

How to implement a Tree data-structure? Provide some code.