Data Structures - Unit 3

1.Explain the different tree traversals with an application? 
. In order
• Explanation with an example
• Figure
. Preorder
• Explanation with an example
• Figure
.
Postorder
• Explanation with an example
• Figure

2. Define binary search tree? Explain the various operations with an example? 
. Definition
. Figure for binary search tree
. Operations
• Codings
• Explanation
• Example


3. Define AVL trees? Explain the LL, RR, RL, LR case with an example? 
. Definition
. LL, RR, RL, LR case
• Figure
• Example
• Explanation

4. Define priority queue? Explain the basic heap operation with an example? 
. Definition
. Basic operation
• Insert
• Delmin
• Delmax
. Coding
. Explanation
. Example

5. Explain any two techniques to overcome hash collision?
. Separate chaining
• Example
• Explanation
• Coding
. Open addressing
• Linear probing
• Quadratic probing 

Data Structures - Unit 3

1.Define post-order traversal? 
Post order traversal entails the following steps;

a. Process the left subtree
b. Process the right subtree
c. Process the root node

2. Define in -order traversal? 
In-order traversal entails the following steps;
a. Process the left subtree
b. Process the root node
c. Process the right subtree

3. What is a balance factor in AVL trees? 
Balance factor of a node is defined to be the difference between the height of the node's left subtree and the height of the node's right subtree.

4. What is meant by pivot node? 
The node to be inserted travel down the appropriate branch track along the way of the deepest level node on the branch that has a balance factor of +1 or -1 is called pivot node.

5. What is the length of the path in a tree? 
The length of the path is the number of edges on the path. In a tree there is exactly one path form the root to each node.

6. Define expression trees? 
The leaves of an expression tree are operands such as constants or variable names and the other nodes contain operators.

Data Structures - Unit 3

1. Define non-linear data structure 
Data structure which is capable of expressing more complex relationship than that of physical adjacency is called non-linear data structure.

2. Define tree? 
A tree is a data structure, which represents hierarchical relationship between individual data items.

3. Define leaf? 
In a directed tree any node which has out degree o is called a terminal node or a leaf.

4. What is meant by directed tree? 
Directed tree is an acyclic diagraph which has one node called its root with indegree o whille all other nodes have indegree I.

5. What is a ordered tree? 
In a directed tree if the ordering of the nodes at each level is prescribed then such a tree is called ordered tree.