Single Linked List Operations and Binary Trees (ISC Class 12 Computer Science)

Understand Single Linked List Operations and Binary Trees

class Node {
    int data; Node next;
    Node(int d) { data = d; next = null; }
}
class LinkedList {
    Node head;                       // null means the list is empty
    boolean isEmpty() { return head == null; }
}

Single Linked List Operations and Binary Trees: key facts

Linked list basics

Empty list	head == null
Last node	next == null
Insert at front	n.next = head, head = n
Delete first	head = head.next

Always check for an empty list first.

Deletion and insertion after a node

• •Delete after t: t.next = t.next.next
• •Insert after t: n.next = t.next, then t.next = n
• •Order of the two assignments matters

Reversing the order loses the rest of the list.

Tree traversals

Preorder	root, left, right
Inorder	left, root, right
Postorder	left, right, root
	Defined recursively

Pre and post give the prefix and postfix forms of an expression tree.

Tree terms

Leaf	no children
Degree	number of children
Depth	edges from the root
Height	edges to the deepest leaf
Size	number of nodes

State the convention used for height and level.

How to answer Single Linked List Operations and Binary Trees questions

1. 1Draw the list as boxes and arrows with head marked; mark the changed arrows after each operation.
2. 2For insertion or deletion, find the node before the position by walking with a temporary reference.
3. 3Handle the special cases: empty list, first node, last node.
4. 4For reversal, trace prev, cur and nxt in a table.
5. 5For a tree, label the root, then find the leaves and the longest path for the height.
6. 6For a traversal, apply the rule at every node recursively: do the left subtree completely before the right.

Single Linked List Operations and Binary Trees in real life

The idea, met in an everyday situation. Answer the question in your own words, then compare with the model answer. The one-line hook is what to remember.

Tricks to remember Single Linked List Operations and Binary Trees

Short memory aids. Say each one aloud once, then use it on a question the same day.

• Link new first, then attach

  Insertion: set the new node's next first, then redirect the old link.

  Use it when: Avoiding a lost list.

• Pre, in, post = where the root is

  Root first, root in the middle, root last.

  Use it when: Tree traversals.

• Three pointers for reversal

  prev, cur, nxt: save next, flip the link, step ahead.

  Use it when: Reversing a list.

• Leaf = no children

  External nodes are the leaves; all others are internal.

  Use it when: Tree terms.

Single Linked List Operations and Binary Trees: solved examples

Ordered from board level to HOTS. Try each one before you open the solution.

void addFront(int x) {
    Node n = new Node(x);
    n.next = head;
    head = n;
}
void addEnd(int x) {
    Node n = new Node(x);
    if (head == null) head = n;
    else {
        Node t = head;
        while (t.next != null) t = t.next;
        t.next = n;
    }
}

void delete(int x) {
    if (head == null) return;
    if (head.data == x) { head = head.next; return; }
    Node t = head;
    while (t.next != null && t.next.data != x)
        t = t.next;
    if (t.next != null)
        t.next = t.next.next;
}

void reverse() {
    Node prev = null, cur = head, nxt;
    while (cur != null) {
        nxt = cur.next;
        cur.next = prev;
        prev = cur;
        cur = nxt;
    }
    head = prev;
}

Where students lose marks in Single Linked List Operations and Binary Trees

The slips examiners see most often, and what to write instead.

• ✗Mistake: Assigning the links in the wrong order

  If t.next is changed first, the rest of the list is lost.

  Wrong working

  t.next = n; n.next = t.next;

  Right working

  n.next = t.next; t.next = n;

  ✓Do this: Attach the new node to the rest first.

  Usually costs: 1 mark

• ✗Mistake: No empty or first-node check

  A null head causes NullPointerException.

  Wrong working

  Node t = head; while (t.next != null) ...

  Right working

  if (head == null) head = n; else { ... }

  ✓Do this: Test head == null at the start.

  Usually costs: 1 mark

• ✗Mistake: Wrong inorder for a missing child

  A missing left child is skipped, not replaced by the root.

  Wrong working

  Inorder of C with only a right child F: F C

  Right working

  Inorder of C with only a right child F: C F

  ✓Do this: Left (none), then root, then right.

  Usually costs: 1 mark

Practice questions on Single Linked List Operations and Binary Trees

Write each answer on paper first. Open the hint only if you are stuck, and the answer only when you have finished.

1. Q1 · 1 mark · MCQBoard level

   The traversal that visits the root first is
   (a) preorder (b) inorder (c) postorder (d) level order only

   Hint

   The prefix "pre" means before.

   Answer

   (a) preorder

2. Q2 · 2 marks · Short answerBoard level

   Give two differences between an array and a single linked list.

   Hint

   Size and insertion.

   Answer

   An array has a fixed size and stores elements in consecutive cells with direct access by index; a linked list grows dynamically, its nodes can be anywhere in memory connected by references, and reaching an item needs a walk from the head. Insertion in the middle of an array needs shifting, while a linked list only changes references.

3. Q3 · 4 marks · Short answerHarder board level

   Write a method int count() for the LinkedList class that returns the number of nodes, and another int sum() that returns the sum of the data. Give both for the list 4, 7, 1.

   Hint

   Use a temporary reference t.

   Answer

   int count() {
       int c = 0;
       for (Node t = head; t != null; t = t.next) c++;
       return c;
   }
   int sum() {
       int s = 0;
       for (Node t = head; t != null; t = t.next) s += t.data;
       return s;
   }

   For 4, 7, 1: count() = 3 and sum() = 12.

4. Q4 · 4 marks · Short answerHarder board level

   Write a method insertSorted(int x) that inserts x into a list that is in ascending order, and show the steps for inserting 6 into 2, 5, 8.

   Hint

   Stop at the node whose next data is not less than x.

   Answer

   void insertSorted(int x) {
       Node n = new Node(x);
       if (head == null || x < head.data) {
           n.next = head;
           head = n;
           return;
       }
       Node t = head;
       while (t.next != null && t.next.data < x)
           t = t.next;
       n.next = t.next;
       t.next = n;
   }

   For 6: head 2 is smaller, so it is not the front. t starts at 2; 5 < 6, so t moves to 5; the next data 8 is not less than 6, so stop. n.next = 8 and 5.next = n. The list is 2, 5, 6, 8.

5. Q5 · 4 marks · Case-basedHOTS / competency

   An expression tree has root *, whose left child is + (with leaves A and B) and whose right child is - (with leaves C and D). (i) Write the preorder, inorder and postorder traversals. (ii) Which two give the prefix and postfix forms? (iii) Why does the inorder result need brackets to mean (A + B) * (C - D)?

   Hint

   Apply the rule at each node.

   Answer

   (i) Preorder: * + A B - C D. Inorder: A + B * C - D. Postorder: A B + C D - *. (ii) Preorder gives the prefix form and postorder gives the postfix form. (iii) Inorder lists the operators between operands but has lost the tree structure, so without brackets the precedence rules would group B * C first.

Test your recall

Answer in your head or on paper first, then open the card. Pulling an answer out of memory makes it stick far better than re-reading.

1. 1.What marks the end of a single linked list?Show answer

   A node whose next is null.

2. 2.Write the inorder rule.Show answer

   Left subtree, root, right subtree.

3. 3.What is a leaf?Show answer

   A node with no children (an external node).

4. 4.What does head == null mean?Show answer

   The list is empty.

5. 5.How do you delete the first node?Show answer

   head = head.next.

6. 6.What is the degree of a node?Show answer

   The number of its children.

Single Linked List Operations and Binary Trees: frequently asked questions