CSS Prepare

optional · CSS study notes

Trees

Definition

  • A Tree is a hierarchical, non-linear data structure consisting of nodes connected by edges, with one designated root node and no cycles

Key Terminology

  • Root: topmost node (no parent)
  • Parent/Child: direct hierarchical relationship
  • Leaf: node with no children
  • Height: longest path from root to a leaf
  • Depth: distance from root to a specific node
  • Subtree: any node + all its descendants, forming a smaller tree

Why Trees Matter

  • Represent hierarchical data naturally (file systems, org charts, XML/HTML DOM, decision trees)
  • Enable efficient search/insert/delete when balanced — O(log n) vs O(n) for linear structures

Tree Traversal Methods (core exam topic)

  • Depth-First:
    • Preorder (Root, Left, Right)
    • Inorder (Left, Root, Right) — gives sorted order for a BST, a key fact
    • Postorder (Left, Right, Root)
  • Breadth-First (Level-order): visit nodes level by level, implemented using a Queue

Exam Angle

Memorize the traversal orders precisely and be ready to trace them on a given tree diagram — a nearly guaranteed question type. The fact that Inorder traversal of a BST yields sorted output is a high-value, frequently tested detail.

📌 Sample & Repeated FPSC Questions (2016–2026)

📝 Exam Practice: Tree Terminology Rapid-Fire (guaranteed short-answer format)

2016, Paper I, Q5(a) (8 marks) — Describe the following (no description with more than three lines): i. Sibling Nodes ii. Degree of a tree iii. Leaf Node iv. Height/Depth of a tree v. Binary Tree vi. Full Binary Tree vii. Complete Binary Tree viii. Maximum number of nodes in a Binary Tree at level L.

Model answer:

  • Sibling Nodes: nodes that share the same immediate parent.
  • Degree of a tree: the maximum number of children possessed by any node in the tree (not just one node — the tree's overall degree).
  • Leaf Node: a node with no children (terminal node) — degree 0.
  • Height/Depth: height is the number of edges on the longest root-to-leaf path; depth of a node is the number of edges from the root to that node.
  • Binary Tree: every node has at most two children (left, right).
  • Full Binary Tree: every node has exactly 0 or exactly 2 children (never just one).
  • Complete Binary Tree: every level is completely filled except possibly the last, which fills strictly left to right.
  • Max nodes at level L: 2L2^L (root at level 0, so level 0 ≤ 1 node, level 1 ≤ 2, level 2 ≤ 4, …).

Exam angle: this exact "define these N terms in ≤3 lines each" format recurs across multiple years — practice one-line, precise definitions rather than paragraphs; examiners cap marks per sub-part regardless of extra detail.

📝 Exam Practice: Tree vs Graph

2018, Paper I, Q6(c) (5 marks) — Differentiate between graph and trees. Which is special case of the other?

Model answer:

TreeGraph
Cyclesnone (acyclic)may contain cycles
Paths between two nodesexactly one unique pathmay have multiple, or none
Edges (n nodes)always exactly n−1any number, up to n(n−1)/2
Hierarchydefined root, parent-childno inherent hierarchy

Key reasoning point: a Tree is a special case of a Graph — specifically, a connected, acyclic (undirected) graph. Every tree is a graph, but not every graph is a tree (only when it additionally satisfies "connected" and "no cycles").

📝 Exam Practice: Types of Trees Beyond Binary

2021, Paper I, Q5(a) (8 marks) — What is a tree in data structure? Describe its types with the help of examples.

Model answer: A tree is a non-linear, hierarchical structure of nodes connected by edges, one root, every other node with exactly one parent, no cycles. Types:

  • Binary Tree — at most two children per node.
  • Binary Search Tree (BST) — left subtree < node < right subtree, enabling O(log n) average search.
  • Balanced trees (AVL, Red-Black) — self-balancing BSTs guaranteeing O(log n) height even worst-case.
  • Heap (Binary Heap) — complete binary tree with the heap-order property; backs priority queues and heapsort.
  • B-Tree / B+ Tree — multi-way balanced trees, each node with many children; used in databases/file systems to minimize disk I/O.
  • Trie (prefix tree) — stores/searches strings by shared prefixes (autocomplete, dictionaries).

📝 Exam Practice: Degree of a Leaf Node (MCQ)

2025, Paper I, Q1 (1 mark) — What is the degree of leaf node in a tree?

  • A. 0 ✓
  • B. 1
  • C. 2
  • D. None of these

MCQ Trap: degree = number of children, not the node's position or number of siblings. A leaf has zero children by definition, so its degree is always 0 — regardless of how deep in the tree it sits or how many siblings surround it.

📜 Past-Paper Questions & MCQs (CSS 2016–2026)

2016 · Paper-I · Q5(a) · 8 marks

Q. Describe the following in no more than three lines each: sibling nodes, degree of a tree, leaf node, height/depth of a tree, binary tree, full binary tree, complete binary tree, and the maximum number of nodes of a binary tree at level L.

Ans.

  • Sibling nodes: nodes that have the same parent.
  • Degree of a tree: the maximum degree (number of children) of any node in the tree.
  • Leaf node: a node with no children (degree 0).
  • Height/depth of a tree: the number of edges on the longest path from the root to a leaf (some books count nodes).
  • Binary tree: a tree in which every node has at most two children, a left and a right child.
  • Full binary tree: every node has either 0 or 2 children.
  • Complete binary tree: all levels are completely filled except possibly the last, which is filled from left to right.
  • Maximum nodes at level L: 2ᴸ, when the root is at level 0 (2ᴸ⁻¹ if the root is at level 1).

2021 · Paper-I · Q5(a) · 8 marks

Q. What is a tree in data structures? Describe its types with the help of examples.

Ans.

  • A tree is a non-linear hierarchical structure of nodes joined by edges. It has one root, every other node has exactly one parent, and there are no cycles. Examples: a file system, an organisation chart.
  • General tree: a node can have any number of children.
  • Binary tree: at most two children per node.
  • Binary search tree (BST): left subtree < node < right subtree, which allows fast search.
  • Balanced trees (AVL, red-black): keep height O(log n) by rotations.
  • Heap: a complete binary tree where each parent is ≥ (max-heap) or ≤ (min-heap) its children, used in priority queues.
  • Other types: B-tree (disk indexes) and trie (strings).
      50
     /  \
   30    70
  /  \     \
20   40     80      (a binary search tree)

MCQs

2025 P-I · Q1. What is the degree of a leaf node in a tree?

  • (A) 0 ✅
  • (B) 1
  • (C) 2
  • (D) None of these
  • Answer: (A) 0.
  • Why: the degree of a node is its number of children. A leaf has no children, so its degree is 0. (The degree of the whole tree is the largest node degree.)