Ch. 1. Question Bank
Chapter 1. Questions and Answers ( Short answer)
Use an example to illustrate the concept of degree and height of a tree.
A degree of a node is the number of children it has. The height of a tree is the longest path from the root to a leaf.
Example:
A
/ | \
B C D
/ \
E F
- Degree of node A = 3 (B, C, D are its children)
- Degree of node B = 2 (E, F are its children)
- Degree of node C = 0 (no children)
- Height of the tree = 2 (maximum number of edges from root A to leaf E or F)
2. Convert the following expression into an expression tree: (A + B) * (C – D).
Expression Tree:
*
/ \
+ –
/ \ / \
A B C D
Write a recursive algorithm for performing an inorder traversal of a binary tree.
Recursive Steps:
- Recursively traverse the left subtree.
- Visit the root node.
- Recursively traverse the right subtree.
- Construct an example to differentiate between a full binary tree and a complete binary tree.
Full Binary Tree: (Every node has 0 or 2 children)
1
/ \
2 3
/ \ / \
4 5 6 7
Complete Binary Tree: (All levels except last are fully filled, and nodes are as left as possible)
1
/ \
2 3
/ \ /
4 5 6
Compare and contrast a strictly binary tree and a full binary tree with examples.
Strictly Binary Tree | Full Binary Tree |
Every internal node has exactly 2 children. | Every node has children. |
every non leaf node must have two children. | Always balanced. all leaf node are at same level. |
Example:
Strictly Binary Tree
1
/ \
2 3
/ \
4 5
Full Binary Tree
1
/ \
2 3
/ \ / \
4 5 6 7
Differentiate between a complete binary tree and a full binary tree with an example.
Complete Binary Tree | Full Binary Tree |
All levels are completely filled except the last. | Every node has children. |
Nodes in the last level are placed from left to right. | Always balanced. all leaf node are at same level.Example: |
Complete Binary Tree
1
/ \
2 3
/ \ /
4 5 6
Full Binary Tree
1
/ \
2 3
/ \ / \
4 5 6 7
- Explain how an expression tree represents arithmetic expressions.
- Operators (+, -, *, /) are internal nodes.
- Operands (A, B, etc.) are leaf nodes.
Example:
Expression: (A + B) * (C – D)
*
/ \
+ –
/ \ / \
A B C D
Construct a static representation of a binary tree using an array.
For a tree:
A
/ \
B C
/ \
D E
Array representation (1-based index):
Index | Value |
1 | A |
2 | B |
3 | C |
4 | D |
5 | E |
Compare the advantages of dynamic representation over static representation in tree implementation.
Comparison of Dynamic Representation vs. Static Representation in Tree Implementation
| Feature | Dynamic Representation (Linked Representation) | Static Representation (Array Representation) |
|---|---|---|
| Memory Utilization | Efficient, as memory is allocated dynamically based on need. | Fixed size, which may lead to wastage or insufficient space. |
| Flexibility | Can grow and shrink dynamically as nodes are added or deleted. | Size is predetermined and cannot be modified easily. |
| Insertion & Deletion | Easy and efficient, as nodes are allocated and deallocated dynamically. | Complex, as shifting of elements may be required. |
| Access Speed | Slower due to pointer traversal for accessing child nodes. | Faster, as direct indexing is used for accessing elements. |
| Implementation Complexity | More complex due to pointer handling. | Simpler as it uses a contiguous memory structure. |
| Use Case | Suitable for dynamic applications where tree size varies. | Suitable for applications with a fixed number of nodes (e.g., complete binary trees). |
Perform an inorder traversal for the given BST:
30
/ \
20 40
/ \ \
10 25 50
Inorder Traversal (Left, Root, Right):
10 → 20 → 25 → 30 → 40 → 50
Apply preorder traversal to a given binary tree and list the node sequence.
A
/ \
B C
/ \
D E
Preorder Traversal (Root, Left, Right):
A → B → D → E → C
