Data Structure Trees Questions for Interview Preparation Set 2

Interview questions on trees in data structures. They are in a brief dossier form. Quick answers have been given to each question. The questions are meant for a fresher preparing for a job interview. Please inform us if you find any mistakes. This is subjective type short answers question and answer set no. 2 in this series.

Last Reviewed and Updated on February 7, 2020
Posted by Parveen(Hoven),
Aptitude Trainer and Software Developer

Interview and Exam Questions and Answers

This set contains a list of commonly asked questions. They are short interview questions aimed at freshers interview, campus placement drives, and also for job interviews. You can use these to have a quick grasp and brush-up of your fundamentals. These questions can be viewed on a mobile phone also because this website is built on responsive web design.

In which traversal method, the root is processed before traversing the left and right subtrees.

In Preorder traversal method, the root is processed before traversing the left and right sub-trees.

What do you mean by Binary tree?

A binary tree is a specific type of tree in which each node can have a maximum of two children. These child nodes are typically distinguished as the left and the right child. The structure of a binary tree is shown in the following figure:


In the preceeding binary tree,node B is the left child of node A, and node C is the right child of node A. Similarly, node D is the left child of node B,and node E is the right child of node B.

What are steps for "in order" traversing a binary tree?

The steps for in order traversing a binary tree are as follows:

  1. Traverse the left subtree
  2. Visit the root
  3. Traverse the right subtree

A min heap is used to sort the list in which order?

A min heap is used to sort the list in descending order.

Which are the various variants of binary tree?

Various variants of binary tree are:

  1. Strictly binary tree: A binary tree is said to be strictly binary if every node, except for the leaf nodes, have non-empty left and right children. A strictly binary tree is shown in following figure:


    In the preceding binary tree, every non-leaf node has precisely two children. Therefore, it is strictly binary tree.

  2. Full binary tree: A binary tree of depth d is said to be a full binary tree if it has exactly 2d-1
  3. Complete binary tree: A binary tree with n nodes and depth d is complete if and only if its nodes correspond to the nodes numbered from 0 to n-1 in the full binary tree of depth k. A complete binary tree is shown in the following figure:

How traversing is done in a binary tree?

Traversing a tree refers to the process of visiting all the nodes of the tree once. There are three ways in which traversing is done such as

  1. Inorder
  2. Preorder
  3. Postorder

How do you define tree in a data structure?

A tree is a nonlinear data structure that represents a hierarchical relationship among the various data elements, as shown in the following figure.

Each data elements in a tree is called a node. The topmost node of the tree is called a root

Which are the various variants of binary tree?

Various variants of binary tree are:

  1. Strictly binary tree: A binary tree is said to be strictly binary if every node, except for the leaf nodes, have non-empty left and right children. A strictly binary tree is shown in following figure:


    In the preceding binary tree, every non-leaf node has precisely two children. Therefore, it is strictly binary tree.

  2. Full binary tree: A binary tree of depth d is said to be a full binary tree if it has exactly 2d-1
  3. Complete binary tree: A binary tree with n nodes and depth d is complete if and only if its nodes correspond to the nodes numbered from 0 to n-1 in the full binary tree of depth k. A complete binary tree is shown in the following figure:

What do you mean by Binary tree?

A binary tree is a specific type of tree in which each node can have a maximum of two children. These child nodes are typically distinguished as the left and the right child. The structure of a binary tree is shown in the following figure:


In the preceeding binary tree,node B is the left child of node A, and node C is the right child of node A. Similarly, node D is the left child of node B,and node E is the right child of node B.

Definitions

How do you define terms:

  1. Siblings/Brothers
  2. Internal node
  3. Level of a node
  4. Depth of a tree

  1. Siblings/Brothers: Children of the same node are called siblings of each other. In the preceding figure:
    1. Nodes 7 and 3 are siblings of each other
    2. Nodes 2 and 6 are siblings of each other
  2. Internal Node: An intermediate node between the root and the leaf nodes is called an internal node. It is also referred to as a non terminal node. In preceding figure, nodes 7,3,6 and 9 are internal nodes
  3. Level of a node: The distance of a node from the root is called the level of a node. The root always lies at level 0. As move down the tree, the level of a node increases in such a way that if a node is at level n, then its children are at level n+1. In preceding figure, level of node 1 is 0, level of nodes 7 and 3 are 1 and so on.
  4. Depth of a tree: The maximum number of levels in a tree is called the depth of a tree. In other words, depth of a tree is one more than maximum level of the tree. The depth of a tree in above figure is 4

My C/C++ Videos on Youtube

Here is the complete playlist for video lectures and tutorials for the absolute beginners. The language has been kept simple so that anybody can easily understand them. I have avoided complex jargon in these videos.