1. Introduction
A tree is a non-linear, hierarchical data structure made of nodes connected by edges, with no cycles. Unlike arrays or linked lists (which are linear), a tree lets us model parent-child relationships - file systems, organization charts, XML/HTML, and the internal machinery of databases all use trees.
For competitive government IT exams (BCS, Bank IT officer, various IT posts), three tree families appear again and again:
- Binary Search Tree (BST) - keeps data ordered so search/insert/delete run fast on average.
- AVL tree - a self-balancing BST that guarantees O(log n) even in the worst case.
- Heap - a complete binary tree used to build priority queues and Heapsort.
Examiners love these because a single tree lets them test terminology (height, degree, leaf), traversals (inorder/preorder/postorder), rotations, and time complexity all at once. Master this lesson and you can answer almost any tree question by hand.
2. Learning objectives
After studying this lesson you will be able to:
- Define every core tree term: node, root, leaf, edge, parent, child, degree, height, depth, level, subtree.
- Distinguish full, complete, perfect, and balanced binary trees.
- Perform BST search, insertion and deletion (all three deletion cases) by hand.
- Compute the three depth-first traversals (inorder, preorder, postorder) and level-order.
- Explain why a plain BST can degrade to O(n) and how AVL fixes it.
- Compute balance factors and apply the four AVL rotations (LL, RR, LR, RL).
- Represent a heap in an array, and run insert (sift-up) and extract (sift-down).
- Build a heap in O(n) and trace Heapsort.
- Choose the right structure and state the correct time complexity for exams.