Past exam question: 2066 Jestha (Back), Q6
Open in the Padhaiko appDefine 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:
- Preorder (
N-L-R):A, B, C, E, I, F, J, D, G, H, K, L - Inorder (
L-N-R):E, I, C, F, J, B, G, D, K, H, L, A - Postorder (
L-R-N):I, E, J, F, C, G, K, L, H, D, B, A
- Complete Binary Tree: All levels full except possibly the last, which fills strictly left-to-right.
- Level-Order Insertion: Uses a queue to insert at the first missing child slot.
- Traversals: Preorder
ABCEIFJDGHKL, InorderEICFJBGDKHLA, PostorderIEJFCGKLHDBA.