PadhaikoAll subjects

Past exam question: 2066 Jestha (Back), Q6

Data Structure and Algorithms · 8 marks

Open in the Padhaiko app

Topic: Definition and tree terminologies · Binary trees · Binary search tree

Question

Define a complete binary tree with an example. Write an algorithm for insertion of a node in binary tree. Write the sequence of node in preorder, inorder and postorder traversal for a given tree.

[figure: binary tree rooted at A; A has only left child B; B has left child C and right child D; C has left child E and right child F; D has left child G and right child H; E has right child I; F has right child J; H has left child K and right child L]

Solution

Complete Binary Tree Definition and Example: A complete binary tree of depth is a binary tree in which every level is completely filled, and all nodes at the last level are packed as far left as possible. Example (5 nodes): 1 has children 2, 3; 2 has children 4, 5 (no gaps on level 2 before 4, 5).

Algorithm for Insertion of a Node in a Binary Tree (Level-Order Insertion):

Algorithm INSERT_BT(root, val):
1. Allocate newNode(val) with left = right = NULL
2. If root == NULL: Return newNode
3. Enqueue root into a FIFO queue Q
4. While !ISEMPTY(Q):
       curr = DEQUEUE(Q)
       If curr->left == NULL:
           curr->left = newNode; Return root
       Else:
           ENQUEUE(Q, curr->left)
       If curr->right == NULL:
           curr->right = newNode; Return root
       Else:
           ENQUEUE(Q, curr->right)

Traversals of the Given Tree:

Answer:

All past exam questions for Data Structure and Algorithms