Introduction: what this topic is and why it matters
This lesson gathers the "high-frequency" advanced data-structure topics that appear again and again in Bangladeshi government job exams (BCS written and preliminary, Bank IT/ICT officer, and various IT-officer posts). These are not random topics — an exam-coverage audit shows that linear vs non-linear classification, expression notation (prefix/postfix) conversion and evaluation, binary-tree leaf/internal-node counting, array representation of trees, Eulerian and Hamiltonian graphs, B-tree / B+ tree basics, O(1) queue with a linked list, queue-with-two-stacks / stack-with-two-queues, and BFS vs DFS together account for a large share of the data-structure marks.
Master this single lesson and you can confidently answer the bulk of the "structure" questions on any of these exams. Every rule here is stated from first principles, every formula is derived, and every calculative item is worked out step by step.
Learning objectives
- Classify any data structure as linear or non-linear and justify the choice.
- Convert expressions between infix, prefix and postfix in all directions, and evaluate prefix/postfix expressions.
- Derive and apply binary-tree counting relations: leaves = internal + 1, k-ary generalisation, nodes at a level, min/max nodes.
- Use the array (implicit) representation of a binary tree: parent i has children 2i and 2i+1.
- State and test the conditions for Eulerian and Hamiltonian paths/circuits.
- Explain B-tree and B+ tree properties and the difference between them.
- Implement an O(1) enqueue/dequeue queue using a singly linked list with front and rear pointers.
- Implement a queue using two stacks and a stack using two queues.
- Choose between BFS and DFS and know their complexity and use-cases.