# Data Structure Trees Questions for Interview Preparation Set 1

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

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

## Write an algorithm to delete a node from a binary search tree.

The following algorithm to locate the node to be deleted and its parent:

1. Make a variable/pointer currentNode point to the ROOT node.
2. Make a variable/pointer parent point to NULL.
3. Repeat steps a,b, and c until currentNode becomes NULL or the value of the node to be searched becomes equal to that of currentNode:
1. Make parent point to currentNode.
2. If the value to be deleted is less than tht of currentNode:
1. Make currentNode point to its left child.
3. If the value to be deleted is greater than that of currentNode:
1. Make currentNode point to its right child.

## Write an algorithm for in order traversing of binary tree.

Algorithm:Inorder(root)

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

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

The steps for preorder traversing a binary tree is as follows:

1. Visit the root
2. Traverse the left sub-tree
3. Traverse the right sub-tree

## State one advantage of a Huffman tree.

A Huffman tree helps assign variable length codes to the characters in a message. It also ensures that the character codes have the prefix property.

## What do you mean by Binary Search Tree?

A binary search tree is a binary tree in which the value of the left child of a node is always less than the value of the node, and the value of the right child of a node is always greater than the value of the node.

The root node contains 52. All the nodes in the left subtree of the root have a value less than 52. Similarly, all the nodes in the right sub-tree of the root node have values greater than 52.

## How is a node searched in binary search tree? Give algorithm for it.

The search operation in binary search tree refers to the process of searching for a specific value in the tree. To perform searching a node in binary search tree following algorithm is used:

1. Make currentNode point to the root node
2. If currentNode is null:
2. Exit
3. Compare the value to be searched with the value of currentNode. Depending on the result of the comparison,there can be three possibilities:
1. If the value is equal to the value of currentNode:
1. Display "Found"
2. Exit
2. If the value is less than the value of currentNode:
1. Make currentNode point to its left child
2. Go to step 2
3. If the value is greater than the value of currentNode:
1. Make currentNode point to its right child
2. Go to step 2

## Define these Terms.

How do you define terms:

1. Leaf node
2. Subtree
3. Children of a node
4. Degree of a node
5. Edge

1. Leaf Node:Anode with no children is called leaf node. They are also referred as terminal nodes. In the given figure,2,5,11 and 4 are leaf nodes
2. Subtree: A portion of a tree, which can be viewed as tree in itself,is called subtree. In preceding figure the tree starting at node 7, containing nodes 2 and 6.A subtree can also contain just one node called the leaf node. In other words, all the leaf nodes are subtrees but all the subtrees are not leaf nodes
3. Children of a node: The roots of the subtrees of a node are called the children of the node. In figure 7 and 3 are children of node 1.
4. Degree of a node: The number of subtrees of a node is called the degree of a node.in given :
1. Degree of node 1 is 2
2. Degree of node 7 is 2
3. Degree of node 3 is 1
5. Edge: A link from the parent to the child node is referred to as edge. It is also known as a branch. A tree with n nodes has n-1 edges.

## Define these Terms.

How do you define terms:

1. Leaf node
2. Subtree
3. Children of a node
4. Degree of a node
5. Edge

1. Leaf Node:Anode with no children is called leaf node. They are also referred as terminal nodes. In the given figure,2,5,11 and 4 are leaf nodes
2. Subtree: A portion of a tree, which can be viewed as tree in itself,is called subtree. In preceding figure the tree starting at node 7, containing nodes 2 and 6.A subtree can also contain just one node called the leaf node. In other words, all the leaf nodes are subtrees but all the subtrees are not leaf nodes
3. Children of a node: The roots of the subtrees of a node are called the children of the node. In figure 7 and 3 are children of node 1.
4. Degree of a node: The number of subtrees of a node is called the degree of a node.in given :
1. Degree of node 1 is 2
2. Degree of node 7 is 2
3. Degree of node 3 is 1
5. Edge: A link from the parent to the child node is referred to as edge. It is also known as a branch. A tree with n nodes has n-1 edges.

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