Question

Data structures Exercises:

For the following binary tree (Index-Value):

0 1 2 3 4 5 6 7 8 9
A C E G B P D X F H

Give the pre-order traversal.
Give the post-order traversal.
Give the in-order traversal.
Determine the height of the tree.

Using these values:
8 6 4 3 5 9 2 1 6

Build a binary search tree.
Build an AVL Tree.
Build a 2-3 Tree.
Build a min-heap.
Build a max-heap.
Apply a heap-sort.

Build an expression tree for the following expressions.
2 + 5
2 * 5 - 3
(2 + 5) * 3
(2 - 5) - (3 + 4) * 5 + 1

Answer 1

Solution:

Binary tree is a tree which has atmost 2 children.

Preorder traversal is a traversal through rootnode, leftnode and rightnode

Postorder traversal is a traversal through leftnode, rightnode and rootnode

Inorder traversal is a traversal through leftnode, rootnode and rightnode.

Height of the tree is the longest number of edges from the rootnode to the leaf node.

Binary search tree is a binary tree where left node is smaller than the root node and right node is greater than the root node.

0 Given, Binary tree: 0 1 2 3 4 5 6 7 8 9 A C E G B PDX FH Now, Constructing wy tree based on given index. -values Pre-Order Traversal: - Based on the binary free, now we generate pre-order traversal. pre-order :- Root, lefto node, right node. pre-order: A, C, G, X, F, B, H, E, P, D] root Explanation. A is root, ust subtree is C, G, B, X, F.H. Next noot is 6, G, X, then x has no children, so we consider F, then B. H and we move to right Sub-tree C, P, D.

post-order Traversal, - Left node, right node, root node. there we consider the teft node right node and last node at the first, then last c) root post-order: [x, F, G, H, B, C, P, D, E, A In-Order Traversal :- Left node, Root Node, Right Node. Here, we consider the left node first, then root node and the right node last. In-Order: TX, G, F, H, B, C, A, P, E, DJ moot right left.

4 Height of the tree ! the tree ! 06 No of edges from hen, we have 3 the root edger node from to the leaf. root to the leaf. tleight of the tree = 3. 5 Givea, 8 6 4 3 5 9 2 1 6 Constructing Binary bearch free! & Binary search bee is a binary free, where left node is less than soot node and right node is greater than root node Step - 1 Step-2:- 648, so eft Step 3 - 4 26, to certo

step. y Step 5 54 Ro right 4. Step 6 938, so right Step & 223, so left of 3.

step- 8 14mm for ఈ00000 This is the resulting Buary bearch tree