# Data Structure Trees Questions for Interview Preparation Set 3

## 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. 3 in this series.

Last Reviewed and Updated on February 7, 2020

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

## Write an algorithm to convert a binary tree into heap.

The following algorithm to convert a binary tree into heap:

1. Set i=(n-1)/2
2. Set j=2i+1
3. Let heap=False
4. Compare the value at index j with the value of its sibling at index j+1:
1. If A[j+1]>A[j]:
2. j=j+1
5. If A[j]>A[(j-1)/2]:

6. Swap A[j] with A[(j-1)/2
j=2j+1
Else
heap=True
7. If((n>j) or(heap=False)),repeat step 4,5, and 6
8. Decrement i by 1
9. If(i>=),repeat steps 2 through 8

## To represent an arithmetic expression binary tree uses three notations which are those notations?

To represent an arithmetic expression binary tree uses three notations those are:

1. Infix notation
2. Prefix notation
3. Postfix notation

## Write an algorithm to convert a binary tree into heap.

The following algorithm to convert a binary tree into heap:

1. Set i=(n-1)/2
2. Set j=2i+1
3. Let heap=False
4. Compare the value at index j with the value of its sibling at index j+1:
1. If A[j+1]>A[j]:
2. j=j+1
5. If A[j]>A[(j-1)/2]:

6. Swap A[j] with A[(j-1)/2
j=2j+1
Else
heap=True
7. If((n>j) or(heap=False)),repeat step 4,5, and 6
8. Decrement i by 1
9. If(i>=),repeat steps 2 through 8

## Write an algorithm for preorder traversing of binary tree.

Algorithm: Preorder(root)

1. If(root=NULL):Exit
2. Visit(root)
3. Preorder(left child of root)
4. Preorder(right child of root)

## Consider the following tree and answer the questions that follow. 1. What is the depth of the tree?
2. Which nodes are the children of node B?
3. Which node is the parent of node F?
4. What is the level of node E
5. Which nodes are the siblings of node H?
6. Which nodes are the siblings of node D?
7. Which nodes are the leaf nodes?
1. 4
2. D and E
3. C
4. 2
5. H does not have any siblings
6. The only sibling of D is E
7. F,G,H and I

## What are the various application fields where binary search trees are used?

Some of them are as follows:

1. Indexing
2. Encoding messages using Huffman tree
3. Arithmetic expression evaluation
4. Sorting data by using Heap tree

## Write an algorithm to insert a node in a binary search tree.

The following is the algorithm to insert a node in a binary search tree:

1. Allocate memory for the new node.
2. Assign value to the data field of new node.
3. Make the left and right child of the new node point to NULL.
4. Locate the node that will be the parent of the node to be inserted. Mark it as parent. Execute the following steps to locate the parent of the new node to be inserted:
1. Mark the root node as currentNode
2. Make parent point to NULL
3. Repeat steps ,e,and f,until currentNode becomes NULL
4. Make parent point to currentNode
5. If the value of the new node is less than that of currentNode:
1. Make currentNode point to its left child
6. If the value of the new node is greater than that of currentNode:
1. Make currentNode point to its right child
5. If parent is NULL(Tree is empty):
1. Mark the new node as ROOT
2. Exit
6. If the value in the data field of the new node is less than that of parent:
1. Make the left child of parent point to the new node
2. Exit
7. If the value in the data field of the new node is greater than that of the parent:
1. Make the right child of parent point to the new node
2. Exit

## 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

## How can a binary tree be represented as a array?

Consider the binary tree with the nodes labeled from 0 to 6,as shown in the following figure. In the preceding binary tree, the node labeled x will be stored at index x in the array. Consider the array representation of preceding binary tree, as shown in the following figure. For any node with index i, n-1>i>0,the following holds true:
1. Parent of i is at index(i-1)/2
2. Left child of i is at index 2i+1. If 2i+1>n-1 there is no left child.
3. Right child of i is at index 2i+2. If 2i+2>n-1 there is no right child

## What are steps for postorder traversing a binary tree?

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

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

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