Data Structure Trees Questions for Interview Preparation Set 3

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]:

Swap A[j] with A[(j-1)/2
j=2j+1
Else
heap=True
6. If((n>j) or(heap=False)),repeat step 4,5, and 6
7. Decrement i by 1
8. 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]:

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

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