1. Can you explain implementation of deletion from a binary tree?

To implement the deletion from a binary tree, there is a need to consider the possibilities of deleting the nodes. They are:

- Node is a terminal node: In case the node is the left child node of its parent, then the left pointer of its parent is set to NULL. In all other cases, if the node is right child node of its parent, then the right pointer of its parent is set to NULL.

- Node has only one child: In this scenario, the appropriate pointer of its parent is set to child node.

- Node has two children: The predecessor is replaced by the node value, and then the predecessor of the node is deleted.

2. Do you know implementation of traversal of a binary tree?

Binary tree traversal is a process of visiting each and every node of the tree. The two fundamental binary tree traversals are ‘depth-first' and ‘breadth-first'.

The depth-first traversal are classified into 3 types, namely, pre-order, in-order and post-order.

Pre-order: Pre-order traversal involves visiting the root node first, then traversing the left sub tree and finally the right sub tree.

In-order: In-order traversal involves visiting the left sub tree first, then visiting the root node and finally the right sub tree.

Post-order: Post-order traversal involves visiting the left sub tree first, then visiting the right sub tree and finally visiting the root node.

The breadth-first traversal is the ‘level-order traversal'. The level-order traversal does not follow the branches of the tree. The first-in first-out queue is needed to traversal in level-order traversal.

3. What is threaded binary tree. Explain its common uses?

A threaded binary tree is structured in an order that, all right child pointers would normally be null and points to the ‘in-order successor' of the node. Similarly, all the left child pointers would normally be null and points to the ‘in-order predecessor' of the node.

- Traversal is faster than unthreaded binary trees
- More subtle, by enabling the determination of predecessor and successor nodes that starts from any node, in an efficient manner.
- Accessibility of any node from any other node
- It is easy to implement to insertion and deletion from a threaded tree.

4. Explain B+ tree? Explain its uses?

B+ tree represents the way of insertion, retrieval and removal of the nodes in a sorted fashion. Every operation is identified by a ‘key'. B+ tree has maximum and minimum bounds on the number of keys in each index segment, dynamically. All the records in a B+ tree are persisted at the last level, i.e., leaf level in the order of keys.

B+ tree is used to visit the nodes starting from the root to the left or / and right sub tree. Or starting from the first node of the leaf level. A bi directional tree traversal is possible in the B+ tree.

5. What is pre-order and in-order tree traversal?

A non-empty binary tree is traversed in 3 types, namely pre-order, in-order and post-order in a recursive fashion.

Pre-order:
Pre-order process is as follows:

- Visit the root node
- Traverse the left sub tree
- Traverse the right sub tree

In-Order:
In order process is as follows:

- Traverse the left sub tree
- Visit the root node
- Traverse the right sub tree

6. How to find the depth of a binary tree?

The depth of a binary tree is found using the following process:

1. Send the root node of a binary tree to a function
2. If the tree node is null, then return false value.
3. Calculate the depth of the left tree; call it ‘d1' by traversing every node. Increment the counter by 1, as the traversing progresses until it reaches the leaf node. These operations are done recursively.
4. Repeat the 3rd step for the left node. Name the counter variable ‘d2'.
5. Find the maximum value between d1 and d2. Add 1 to the max value. Let us call it ‘depth'.
6. The variable ‘depth' is the depth of the binary tree.

7. Explain binary tree? Explain its uses?

A binary tree is a tree structure, in which each node has only two child nodes. The first node is known as root node. The parent has two nodes namely left child and right child.

Uses of binary tree:

- To create sorting routine.
- Persisting data items for the purpose of fast lookup later.
- For inserting a new item faster

8. Explain ree database. Explain its common uses?

A tree is a data structure which resembles a hierarchical tree structure. Every element in the structure is a node. Every node is linked with the next node, either to its left or to its right. Each node has zero or more child nodes. The length of the longest downward path to a leaf from that node is known as the height of the node and the length of the path to its root is known as the depth of a node.

Common Uses:

- To manipulate hierarchical data
- Makes the information search, called tree traversal, easier.
- To manipulate data that is in the form of sorted list.
- To give visual effects for digital images using as a work flow by compositing them.

9. Explain a B+ tree?

It is a dynamic, multilevel index, with maximum and minimum bounds on the number of keys in each index segment. all records are stored at the lowest level of the tree; only keys are stored in interior blocks.

10. What is threaded binary trees?

In a threaded binary tree, if a node 'A' has a right child 'B' then B's left pointer must be either a child, or a thread back to A.

In the case of a left child, that left child must also have a left child or a thread back to A, and so we can follow B's left children until we find a thread, pointing back to A.

This data structure is useful when stack memory is less and using this tree the treversal around the tree becomes faster.