The Project | About Us | Contribute | Donations | License

HOME

In this section, we will provide a series of exercises to help you practice and reinforce your understanding of tree data structures. These exercises will cover various types of trees, including binary trees, binary search trees, AVL trees, and B-trees. Each exercise will be followed by a detailed solution to help you check your work and understand the concepts better.

Exercise 1: Binary Tree Traversal

Problem: Given the following binary tree, perform the in-order, pre-order, and post-order traversals.

Solution:

In-order Traversal (Left, Root, Right):

Visit left subtree
Visit root
Visit right subtree

def in_order_traversal(root):
    if root:
        in_order_traversal(root.left)
        print(root.data, end=' ')
        in_order_traversal(root.right)

# Output: 4 2 5 1 3 6

Pre-order Traversal (Root, Left, Right):

Visit root
Visit left subtree
Visit right subtree

def pre_order_traversal(root):
    if root:
        print(root.data, end=' ')
        pre_order_traversal(root.left)
        pre_order_traversal(root.right)

# Output: 1 2 4 5 3 6

Post-order Traversal (Left, Right, Root):

Visit left subtree
Visit right subtree
Visit root

def post_order_traversal(root):
    if root:
        post_order_traversal(root.left)
        post_order_traversal(root.right)
        print(root.data, end=' ')

# Output: 4 5 2 6 3 1

Exercise 2: Binary Search Tree Insertion

Problem: Insert the following values into an empty binary search tree (BST) in the given order: 7, 3, 10, 1, 5, 8, 12.

Solution:

class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.data = key

def insert(root, key):
    if root is None:
        return Node(key)
    else:
        if root.data < key:
            root.right = insert(root.right, key)
        else:
            root.left = insert(root.left, key)
    return root

# Create the BST
root = None
values = [7, 3, 10, 1, 5, 8, 12]
for value in values:
    root = insert(root, value)

# In-order traversal to check the structure
in_order_traversal(root)  # Output: 1 3 5 7 8 10 12

Exercise 3: AVL Tree Rotation

Problem: Insert the following values into an empty AVL tree: 10, 20, 30. Show the tree structure after each insertion and explain the rotations performed.

Solution:

Insert 10:
```
    10
```
Insert 20:
```
    10
      
          20
```

Insert 30:

After inserting 30, the tree becomes unbalanced:

Perform a left rotation on 10:
```
    20
   /  
       10   30
```

Exercise 4: B-Tree Insertion

Problem: Insert the following values into an empty B-tree of order 3: 10, 20, 5, 6, 12, 30, 7, 17. Show the tree structure after each insertion.

Solution:

Insert 10:
```
[10]
```
Insert 20:
```
[10, 20]
```
Insert 5:
```
[5, 10, 20]
```
Insert 6:
- Split the node as it exceeds the order:
```
[10]
/  
   [5, 6] [20]
```
Insert 12:
```
  [10]
  /  
   [5, 6] [12, 20]
```
Insert 30:
```
  [10]
  /  
   [5, 6] [12, 20, 30]
```

Insert 7:

Split the node as it exceeds the order:

[10, 20]
/   |   
   [5, 6, 7] [12] [30]

Insert 17:

  [10, 20]
  /   |   
   [5, 6, 7] [12, 17] [30]

Conclusion

In this section, we have covered various exercises related to tree data structures, including binary trees, binary search trees, AVL trees, and B-trees. By working through these exercises, you should have gained a deeper understanding of tree operations and their implementations. Make sure to practice these exercises to reinforce your knowledge and prepare for more advanced topics in data structures.

Exercises with Trees

Exercise 1: Binary Tree Traversal

Exercise 2: Binary Search Tree Insertion

Exercise 3: AVL Tree Rotation

Exercise 4: B-Tree Insertion

Conclusion

Data Structures Course

Module 1: Introduction to Data Structures

Module 2: Lists

Module 3: Stacks

Module 4: Queues

Module 5: Trees

Module 6: Graphs

Module 7: Conclusions and Additional Resources