Binary Search Tree Homework Solutions#
Assignment: Written Portion (BST Insertion & Traversals)
Problem 1: BST Insertion Sequences#
Draw the binary search tree that results from inserting each sequence of numbers into an initially empty tree.
Rules for Binary Search Tree Insertion:
The first inserted value becomes the Root.
For each subsequent value, compare it with the current node:
If the value is less than the current node, move to the left child.
If the value is greater than the current node, move to the right child.
Repeat until an empty spot is found, then insert the value as a new leaf node.
Sequence A#
Sequence: 8, 3, 10, 1, 6, 14, 4, 7, 13
Insertion Steps:#
8: Root node.
3: \(3 < 8 \rightarrow\) Left child of
8.10: \(10 > 8 \rightarrow\) Right child of
8.1: \(1 < 8, 1 < 3 \rightarrow\) Left child of
3.6: \(6 < 8, 6 > 3 \rightarrow\) Right child of
3.14: \(14 > 8, 14 > 10 \rightarrow\) Right child of
10.4: \(4 < 8, 4 > 3, 4 < 6 \rightarrow\) Left child of
6.7: \(7 < 8, 7 > 3, 7 > 6 \rightarrow\) Right child of
6.13: \(13 > 8, 13 > 10, 13 < 14 \rightarrow\) Left child of
14.
Tree Structure:#
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
Sequence B#
Sequence: 15, 6, 18, 3, 7, 17, 20, 2, 4, 13, 9
Insertion Steps:#
15: Root node.
6: \(6 < 15 \rightarrow\) Left child of
15.18: \(18 > 15 \rightarrow\) Right child of
18.3: \(3 < 15, 3 < 6 \rightarrow\) Left child of
6.7: \(7 < 15, 7 > 6 \rightarrow\) Right child of
6.17: \(17 > 15, 17 < 18 \rightarrow\) Left child of
18.20: \(20 > 15, 20 > 18 \rightarrow\) Right child of
18.2: \(2 < 15, 2 < 6, 2 < 3 \rightarrow\) Left child of
3.4: \(4 < 15, 4 < 6, 4 > 3 \rightarrow\) Right child of
3.13: \(13 < 15, 13 > 6, 13 > 7 \rightarrow\) Right child of
7.9: \(9 < 15, 9 > 6, 9 > 7, 9 < 13 \rightarrow\) Left child of
13.
Tree Structure:#
15
/ \
6 18
/ \ / \
3 7 17 20
/ \ \
2 4 13
/
9
Problem 2: Tree Traversals#
Given the binary search trees, determine the node visit order for Preorder, Inorder, and Postorder traversals.
Tree 1#
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
Traversal Definitions & Order:#
Preorder (Root, Left, Right)
Order:
8, 3, 1, 6, 4, 7, 10, 14, 13
Inorder (Left, Root, Right)
Order:
1, 3, 4, 6, 7, 8, 10, 13, 14
Postorder (Left, Right, Root)
Order:
1, 4, 7, 6, 3, 13, 14, 10, 8
Tree 2#
20
/ \
10 30
/ \ / \
5 15 25 35
/ \
2 18
Traversal Definitions & Order:#
Preorder (Root, Left, Right)
Order:
20, 10, 5, 2, 15, 18, 30, 25, 35
Inorder (Left, Root, Right)
Order:
2, 5, 10, 15, 18, 20, 25, 30, 35
Postorder (Left, Right, Root)
Order:
2, 5, 18, 15, 10, 25, 35, 30, 20