GATE CS - PROGRAMMING & DATA STRUCTURES:Trees

Trees for GATE CS

GATE tree questions ask you to compute height/nodes, reconstruct from traversals, or trace BST insert/delete. Heaps and AVL rotations show up as “what is the tree after…” diagrams. Definitions without a worked trace will not save marks.

Facts that show up as 1-mark questions

• Tree on $n$ nodes: $n-1$ edges, connected, acyclic
• Binary tree: max nodes at level $i$ (root level 0) = $2^i$
• Perfect binary tree height $h$: $2^{h+1}-1$ nodes (if height counted in edges from root — match the question’s height convention)
• Min height for $n$ nodes (binary): $\lceil \log_2(n+1)\rceil - 1$ or similar — derive from the formula they use

Traversals

Reconstruction: inorder + preorder (or inorder + postorder) uniquely determine a binary tree. Preorder + postorder alone do not (ambiguous without more info).

Worked: BST insert sequence

Insert into empty BST: 50, 30, 70, 20, 40

      50
     /  \
   30    70
  /  \
20   40

Inorder of a BST is always sorted: 20, 30, 40, 50, 70.

Delete in BST: leaf — remove; one child — bypass; two children — replace with inorder successor (or predecessor), then delete that node.

AVL (balance)

Balance factor = height(left) − height(right), must stay in {−1,0,1}. Insertions may need LL, RR, LR, RL rotations. GATE usually gives a tree and asks which rotation restores balance — draw the pivot, not the whole textbook case table from memory.

Heap reminder

Complete binary tree; max-heap: parent ≥ children. Insert at next leaf then bubble up; extract-max: replace root with last leaf, sift down. Array index: children of $i$ at $2i+1$, $2i+2$ (0-based).

Next: Graphs. Practice: GATE hub.