Trees in Data Structures: Binary Trees, Traversals, BST, AVL and Heaps · ডেটা স্ট্রাকচারে ট্রি: বাইনারি ট্রি, ট্রাভার্সাল, বিএসটি, এভিএল ও হিপ

1. Tree terms

A tree stores data in a hierarchy, like a family tree or the folders on a disk. It is non-linear: one node can lead to several others.

Term	Meaning
Node	One element of the tree (holds a key or value)
Edge	The link between a parent and a child
Root	The top node; the only node with no parent
Parent, child, siblings	A node directly above, directly below; nodes with the same parent
Leaf (external node)	A node with no children
Internal node	A node with at least one child
Degree of a node	Its number of children; the degree of a tree is the largest node degree
Depth of a node	The number of edges from the root down to it (the root has depth 0)
Height of a node	The number of edges on the longest path from it down to a leaf (a leaf has height 0)
Height of the tree	The height of the root (= the largest depth)
Level	All nodes at the same depth; level 0 or level 1 for the root, depending on the textbook
Subtree	A node together with all its descendants
Ancestor, descendant	Any node on the path up to the root; any node below

Two facts follow straight from the definition: a tree with n nodes has n − 1 edges (every node except the root has exactly one edge to its parent), and there is exactly one path between any two nodes.

The height convention. This page counts height in edges, so a single node has height 0. Some books and questions count nodes (a single node has height 1) or number the levels from 1. Both are fine, but every formula shifts by one, so first check which one the question uses.

2. Binary trees and their formulas

A binary tree is a tree in which each node has at most two children, called left and right; a node may have 0, 1 or 2 children. Left and right are different positions, so a node with only a left child is a different tree from one with only a right child.

Fact	Height counted in edges (root at 0)	Levels counted from 1 (N levels)
Maximum nodes on one level	Level d holds at most 2ᵈ nodes	Level l holds at most 2ˡ⁻¹
Maximum nodes in the tree	2ʰ⁺¹ − 1	2ᴺ − 1
Minimum nodes for that height	h + 1 (a skewed chain)	N
Minimum height for n nodes	⌈log₂(n + 1)⌉ − 1	⌈log₂(n + 1)⌉
Maximum height for n nodes	n − 1 (skewed)	n

Check: a perfect tree of height 2 has 1 + 2 + 4 = 7 = 2³ − 1 nodes. With 100 nodes the height is at least ⌈log₂ 101⌉ − 1 = 6 and at most 99.

More counting facts that exams use:

• Leaves vs nodes of degree 2. In any non-empty binary tree, n₀ = n₂ + 1: the number of leaves is one more than the number of nodes with two children.
• Full (proper) binary tree, where every node has 0 or 2 children: leaves = internal nodes + 1, so n = 2I + 1 is always odd. Proof: n = L + I nodes and n − 1 edges; each internal node gives exactly 2 edges, so n − 1 = 2I, which gives L + I − 1 = 2I, so L = I + 1. Its maximum height is (n − 1)/2: an 11-node full binary tree can have height 5.
• Number of different binary tree shapes with n unlabelled nodes is the Catalan number C(2n, n)/(n + 1): 1, 2, 5, 14, 42 for n = 1 to 5. With labelled nodes multiply by n! (30 trees for 3 labelled nodes).
• Full k-ary tree (every internal node has exactly k children) with n internal nodes has n(k − 1) + 1 leaves.
• Null links. A binary tree with n nodes has 2n link fields but only n − 1 are used (one per edge), so n + 1 links are NULL.
• The empty tree is a binary tree under the usual recursive definition, so the "minimum number of nodes in a binary tree" is 0 (and h + 1 for a given height h).

3. Full, complete and perfect binary trees

Type	Rule	Example property
Full (strict, proper)	Every node has 0 or 2 children	Leaves = internal nodes + 1
Complete	Every level is full except possibly the last, which is filled from the left	Fits in an array with no gaps; the shape of a heap
Perfect	All internal nodes have 2 children and all leaves are on the same level	Exactly 2ʰ⁺¹ − 1 nodes and 2ʰ leaves
Balanced	Left and right heights differ by a small bound at every node	Height stays O(log n)
Skewed (degenerate)	Every node has at most one child	Behaves like a linked list

A perfect tree is both full and complete. Names vary: some books call a perfect tree "complete" or "full". So the MCQ "a complete binary tree of height n has how many nodes?" keys 2ⁿ⁺¹ − 1, which is really the perfect-tree count (the most a complete tree can hold).

Array form. A complete tree is stored level by level in an array. With indices from 1, node i has children at 2i and 2i + 1 and its parent at ⌊i/2⌋; with indices from 0, the children are at 2i + 1 and 2i + 2 and the parent at ⌊(i − 1)/2⌋.

4. Traversals, with one worked tree

A traversal visits every node once. The three depth-first orders differ only in when the root is visited:

Traversal	Order	Uses
Preorder	Root, Left, Right	Copying a tree; prefix (Polish) form of an expression; the first value is the root
Inorder	Left, Root, Right	Sorted output of a BST; infix form of an expression
Postorder	Left, Right, Root	Deleting a tree (children before parent); postfix form; the last value is the root
Level order	Level by level, left to right	Breadth-first search, done with a queue

Depth-first traversals use a stack (the recursion stack); level order uses a queue. All four take O(n) time.

Worked example 1: all four orders of one tree.

1. Preorder (root first): visit A, then all of A's left subtree in preorder (B, D, E, G), then the right subtree (C, F): A B D E G C F.
2. Inorder (root in the middle): the left subtree of B is D, so D, B; then E's subtree in inorder is G, E; then A; then C's subtree (C has no left child, so C, then F): D B G E A C F.
3. Postorder (root last): D, then G, E, then B; then F, C; finally A: D G E B F C A.
4. Level order: level 0 A; level 1 B, C; level 2 D, E, F; level 3 G: A B C D E F G.

A variant asked in one paper: "right child first, then left child, finally the root". On this tree that gives F C G E D B A, which is exactly the preorder read backwards. That is always true, because reversing Root-Left-Right at every node gives Right-Left-Root.

Expression trees. The expression (a + b) × (c − d) is a tree with × at the root, + and − as its children, and the variables as leaves. Preorder gives the prefix form × + a b − c d, postorder the postfix form a b + c d − ×, and inorder (with brackets) the infix form.

5. Rebuilding a tree from two traversals

Inorder + preorder (or inorder + postorder) fixes exactly one binary tree when the keys are distinct. Preorder's first value (or postorder's last) is the root; finding it in the inorder list splits the rest into the left and right subtrees; repeat on each part.

Worked example 2. Preorder: 1 2 4 5 7 8 3 6. Inorder: 4 2 7 5 8 1 3 6. Draw the tree.

1. The root is 1 (first in preorder). In the inorder list, 4 2 7 5 8 lies left of 1 and 3 6 lies right.
2. Left part: the next preorder value is 2, so 2 is the left child of 1. In the inorder piece 4 2 7 5 8: 4 is left of 2, and 7 5 8 is right of 2.
3. Under 2: the left child is 4 (a leaf). For 7 5 8, the next preorder value is 5, so 5 is the right child of 2, with 7 on its left and 8 on its right.
4. Right part (3 6): the next preorder value is 3; in the inorder piece 3 6 nothing is left of 3, so 6 is its right child.

Check: the postorder of this tree is 4 7 8 5 2 6 3 1. A program rebuilding the tree from the two lists produced the same preorder and inorder.

Preorder + postorder is not enough in general: a node with one child gives the same two lists whether the child is on the left or the right. It does fix the tree when the tree is full (every node has 0 or 2 children). Example from a past paper: pre = 1 2 4 8 9 5 3 6 7 and post = 8 9 4 5 2 6 7 3 1 rebuild to root 1 with children 2 and 3; 2 has children 4 and 5; 4 has 8 and 9; 3 has 6 and 7. Its inorder is 8 4 9 2 5 1 6 3 7.

6. Binary search trees (BST)

A BST is a binary tree in which, for every node, all keys in the left subtree are smaller and all keys in the right subtree are larger (duplicates need a fixed rule, such as "equal goes right"). So the inorder traversal gives the keys in ascending order; it never gives descending order (Right, Root, Left would).

• Search: compare with the node; go left if smaller, right if larger; stop when found or at an empty link.
• Insert: search for the key; it is placed where the search falls off the tree, so a new key is always a leaf.
• Delete, three cases: a leaf is simply removed; a node with one child is replaced by that child; a node with two children takes the key of its inorder successor (the smallest key in its right subtree, found by going right once and then left as far as possible) or of its inorder predecessor, and that node is then deleted instead.

Worked example 3. Insert 60, 25, 72, 15, 30, 68, 13, 18 into an empty BST.

1. 60 is the root. 25 < 60 goes left; 72 > 60 goes right.
2. 15: left of 60, left of 25. 30: left of 60, right of 25. 68: right of 60, left of 72.
3. 13: left, left, left of 15. 18: left, left, right of 15.

• The left subtree of the root has 5 nodes (25, 15, 30, 13, 18), a keyed MCQ answer.
• Inorder: 13 15 18 25 30 60 68 72 (sorted). Preorder: 60 25 15 13 18 30 72 68. Postorder: 13 18 15 30 25 68 72 60.
• Delete 13 (a leaf): just remove it. Delete 72 (one child): 68 takes its place.
• Delete 25 (two children): its inorder successor is 30 (the right subtree is the single node 30). Copy 30 into 25's place and remove the old 30. The tree becomes 60 → left 30 (with 15, 13, 18 below it) and right 72 → 68, and the inorder is still sorted.

BST operation	Balanced (height ≈ log₂ n)	Skewed (height n − 1)
Search	O(log n)	O(n)
Insert	O(log n)	O(n)
Delete	O(log n)	O(n)

Inserting keys in sorted order (1, 2, 3, …) builds a skewed tree, which is no better than a linked list. That is why balanced trees exist.

7. AVL trees: rotation basics

An AVL tree (Adelson-Velsky and Landis, 1962) is a BST in which, at every node, the heights of the left and right subtrees differ by at most 1. The balance factor BF = height(left) − height(right) must be −1, 0 or +1. Its height stays below about 1.44 log₂ n, so search, insert and delete are O(log n) even in the worst case.

After an insertion, walk up from the new node to the first node with BF = +2 or −2 and fix it:

Case	The new key went into …	Fix
LL	the left subtree of the left child	One right rotation at the unbalanced node
RR	the right subtree of the right child	One left rotation
LR	the right subtree of the left child	Left rotation at the child, then right rotation at the node
RL	the left subtree of the right child	Right rotation at the child, then left rotation at the node

A rotation moves only a few pointers, takes O(1) time and keeps the inorder (sorted) order.

Worked example 4. Insert 30, 20, 10, 25, 28 into an empty AVL tree.

1. 30, 20, 10: node 30 gets BF = +2 and 10 went left of its left child: LL, so rotate right at 30. Root 20, children 10 and 30.
2. 25 goes left of 30. All balance factors are within −1 … +1 (20 has BF −1, 30 has +1).
3. 28 goes right of 25. Now 30 has BF = +2, and 28 went into the right subtree of its left child 25: LR. Rotate left at 25 (28 moves up), then right at 30.
4. Result: root 20; left 10; right 28 with children 25 and 30. Every BF is now 0 or −1 (the root's).

Fewest nodes in an AVL tree of height h (root at height 0): N(h) = N(h − 1) + N(h − 2) + 1, with N(0) = 1 and N(1) = 2, giving 1, 2, 4, 7, 12, 20. A red-black tree is another self-balancing BST: it colours each node red or black and keeps every root-to-leaf path within twice the length of any other, so it too guarantees O(log n).

8. Heaps and heap sort

A binary heap is a complete binary tree with the heap property: in a max-heap every parent ≥ its children, so the largest key is at the root; in a min-heap every parent ≤ its children. A heap is not a BST: siblings have no order, so searching for an arbitrary key costs O(n).

• Insert: put the key in the next free array slot and sift it up (swap with its parent while it breaks the heap rule): O(log n).
• Delete the root (extract max or min): move the last key to the root and sift it down (swap with the larger child in a max-heap, the smaller in a min-heap): O(log n).
• Peek at the root: O(1). Build a heap from n keys by sifting down from the last internal node back to the root: O(n), not O(n log n).

Worked example 5: min-heap insertions. Insert 9, 3, 7, 4, 8, 2, 6, 5 into an empty min-heap (array shown after each insertion).

Insert	What happens	Array
9	Becomes the root	9
3	3 < 9: swap	3, 9
7	7 > 3: stays	3, 9, 7
4	4 < 9: swap; 4 > 3: stop	3, 4, 7, 9
8	8 > 4: stays	3, 4, 7, 9, 8
2	2 < 7: swap; 2 < 3: swap to the root	2, 4, 3, 9, 8, 7
6	6 > 3: stays	2, 4, 3, 9, 8, 7, 6
5	5 < 9: swap; 5 > 4: stop	2, 4, 3, 5, 8, 7, 6, 9

An array that is already in ascending order, such as 12, 29, 33, 56, 66, 99, 100, 344, is already a valid min-heap: every parent is smaller than the keys after it.

Heap sort builds a max-heap, then repeatedly swaps the root (the maximum) to the end of the array and sifts the new root down in the shrunken heap. For 4, 10, 3, 5, 1: building gives 10, 5, 3, 4, 1; the passes give 5, 4, 3, 1 | 10, then 4, 1, 3 | 5, 10, and finally 1, 3, 4, 5, 10. It runs in O(n log n) time in every case, in place, but is not stable. Its comparison with the other sorts is on the sorting algorithms page.

9. B-trees in brief

A B-tree of order m is a balanced search tree built for disks and databases, where each node is one disk block holding many keys, so the tree is short and few blocks are read.

• Every node has at most m children and m − 1 keys, kept in sorted order. (Some textbooks use the minimum degree t instead: at most 2t − 1 keys, and at least t − 1 in a non-root node. Check which definition the question uses.)
• Every internal node except the root has at least ⌈m/2⌉ children (so at least ⌈m/2⌉ − 1 keys); the root has at least 2 children unless it is a leaf.
• All leaves are on the same level, so the tree is always balanced; search, insert and delete are O(log n).
• A full node is split on insertion: its middle key moves up to the parent, so the tree grows at the root. In an order-3 B-tree, inserting 10, 20, 30 overflows the node [10, 20, 30], so 20 moves up: root [20] with children [10] and [30]. Adding 40 and 50 splits [30, 40, 50] and sends 40 up: root [20, 40] with children [10], [30] and [50].
• A B+ tree keeps all records in the leaves, uses internal nodes only as an index, and links the leaves in order, which makes range queries fast. Database indexes and file systems mostly use B+ trees.

10. Tricky exam cases

1. "How many children does a binary tree node have?" 0, 1 or 2 (at most two), not "exactly 2".
2. Which traversal deletes children before their parent? Postorder. Which sorts a BST? Inorder. Level order is breadth-first search.
3. Height from postorder + inorder. Post 8 9 6 7 4 5 2 3 1 with in 8 6 9 4 7 2 5 1 3 rebuilds to root 1 with left child 2 and right child 3; the longest path 1 → 2 → 4 → 6 → 8 has 4 edges, the keyed height.
4. A BST from its preorder. Preorder 40 20 10 30 60 50 70 of a BST gives the tree directly (the inorder is just the sorted list), so its postorder is 10 30 20 50 70 60 40.
5. Max-heap minimum. The largest key of a max-heap is at the root, but the smallest can be any leaf; finding it, or any arbitrary key, takes O(n).
6. Suffix trees and tries are trees over strings: a suffix tree answers "does pattern P occur in text T?" in time proportional to the length of P, so its use is fast string search.
7. Mirror a binary tree: swap the left and right child of every node, recursively (in any of the depth-first orders). Inorder of the mirror is the reverse of the original inorder.
8. Threaded binary tree: the n + 1 NULL links of a binary tree are reused as "threads" to the inorder predecessor or successor, so inorder traversal needs no stack or recursion.