What are common examiner traps in Trees?

Height definition confusion: GATE consistently defines height as the number of edges on the longest path (leaf height = 0, root-only tree height = 0), not number of nodes/levels. Assuming binary tree traversal rules on general multi-way trees without properly applying leftmost-child -> root -> remaining-children definition. LCRS representation misinterpretation: forgetting that in left-child right-sibling, a node is a leaf in the original tree if and only if its leftMostChild is NULL. Parenthesization/operator associativity errors when converting postfix expression strings into binary expression trees. Off-by-one errors in node counting when confusing total internal nodes (n1 + n2) with strictly degree-2 internal nodes (n2).

Trees

13 Qs · since 2012 · 17 marks · 0.7 marks/paperStandard yield

Take topic test

In GATE CS, the 'Trees' topic tests structural counting relations in binary trees, tree traversal techniques (standard, custom, and multi-way tree traversals), tree reconstruction… Guide

Type

GATE CSE 2026 Set 2Q12MCQ1 markEasyDiagramThe set $\mathbf{T}$ represents various traversals over binary tree. The set $\mathbf{S}$ represents the order of visiting nodes during a traversal. Which one of the following is the correct match from $\mathbf{T}$ to $\mathbf{S}$ ?
GATE CSE 2025 Set 2Q13MCQ1 markEasyConsider a binary tree $T$ in which every node has either zero or two children. Let $n > 0$ be the number of nodes in $T$ . Which ONE of the following is the number of nodes in $T$ that have exactly two children?
GATE CSE 2021 Set 2Q16NAT1 markEasyConsider a complete binary tree with 7 nodes. Let $A$ denote the set of first 3 elements obtained by performing Breadth-First Search (BFS) starting from the root. Let $B$ denote the set of first 3 elements obtained by performing Depth-First Search (DFS) starting from the root. The value of $|A - B|$ is ________.
GATE CSE 2018Q20NAT1 markMediumThe postorder traversal of a binary tree is 8,9,6,7,4,5,2,3,1. The inorder traversal of the same tree is 8,6,9,4,7,2,5,1,3. The height of a tree is the length of the longest path from the root to any leaf. The height of the binary tree above is ________.
GATE CSE 2016 Set 2Q11NAT1 markEasyBreadth First Search (BFS) is started on a binary tree beginning from the root vertex. There is a vertex $t$ at a distance four from the root. If $t$ is the $n$ -th vertex in this BFS traversal, then the maximum possible value of $n$ is _________.
GATE CSE 2016 Set 2Q36MCQ2 marksMediumConsider the following $\text{New-order}$ strategy for traversing a binary tree: • Visit the root;• Visit the right subtree using $\text{New-order}$ ; • Visit the left subtree using $\text{New-order}$ ; The $\text{New-order}$ traversal of the expression tree corresponding to the reverse polish expression 3 4 * 5 - 2 ^ 6 7 * 1 + -…
GATE CSE 2015 Set 1Q25MCQ1 markEasyThe height of a tree is the length of the longest root-to-leaf path in it. The maximum and minimum number of nodes in a binary tree of height 5 are
GATE CSE 2015 Set 2Q10NAT1 markEasyA binary tree T has 20 leaves. The number of nodes in T having two children is ______.
GATE CSE 2015 Set 3Q25NAT1 markEasyConsider a binary tree T that has 200 leaf nodes. Then, the number of nodes in T that have exactly two children are _____.
GATE CSE 2014 Set 2Q39NAT2 marksMediumDiagramConsider the expression tree shown. Each leaf represents a numerical value, which can either be 0 or 1. Over all possible choices of the values at the leaves, the maximum possible value of the expression represented by the tree is _____.
GATE CSE 2014 Set 3Q12MCQ1 markMediumDiagramConsider the following rooted tree with the vertex labeled P as the root: The order in which the nodes are visited during an in-order traversal of the tree is
GATE CSE 2014 Set 3Q41MCQ2 marksMediumConsider the pseudocode given below. The function DoSomething() takes as argument a pointer to the root of an arbitrary tree represented by the leftMostChild-rightSibling representation. Each node of the tree is of type treeNode. typedef struct treeNode* treeptr; struct treeNode { treeptr leftMostChild, rightSibling; }; int DoSomething (treeptr tree) { int value=0; if (tree != NULL) { if (tree->leftMostChild == NULL) value = 1; else value = DoSomething(tree->leftMostChild); value = value + DoSomething(tree->rightSibling); } return(value); }…
GATE CSE 2012Q47MCQ2 marksEasyThe height of a tree is defined as the number of edges on the longest path in the tree. The function shown in the pseudocode below is invoked as height(root) to compute the height of a binary tree rooted at the tree pointer root. int height (treeptr n) { if (n == NULL) return -1; if (n -> left == NULL) if (n -> right == NULL) return 0; else return B1 ; // Box 1 else { h1 = height (n -> left); if (n -> right == NULL) return (1+h1); else { h2 = height (n -> right); return B2 ; // Box 2 } } }…

Topic guide

What does GATE test in Trees?

In GATE CS, the 'Trees' topic tests structural counting relations in binary trees, tree traversal techniques (standard, custom, and multi-way tree traversals), tree reconstruction from sequences, expression tree evaluations, and recursive algorithms over binary/multi-way tree representations. Questions are heavily weighted towards 1-mark foundational items (both MCQ and NAT) with 2-mark questions focusing on code analysis or expression optimization.

Core concepts

Binary tree node degree properties and counting relations
Tree height definition (number of edges on the longest root-to-leaf path)
Standard tree traversals: Inorder, Preorder, Postorder, and Level-order (BFS)
General tree inorder traversal and Left-Child Right-Sibling (LCRS) representation
Binary tree reconstruction from Inorder + Postorder or Inorder + Preorder
Expression tree construction from reverse Polish (postfix) notation and evaluation
Breadth-First Search (BFS) vs Depth-First Search (DFS) traversal differences

Recurring question patterns

Binary Tree Structural Counting & Node Degree Relations
common · mixed · 1 marks · 2025, 2015
Using handshaking/edge-node relations ( $n_0 = n_2 + 1$ , $n = 2n_2 + 1$ for strictly binary trees, or min/max nodes given height $h$ ) to find counts of leaves, full nodes, or total nodes.
Tree Reconstruction & Traversal Order Evaluation
common · mixed · 1.5 marks · 2026, 2018, 2016, 2014
Reconstructing a binary tree from combinations of traversals (e.g., inorder + postorder) to compute properties like height, or computing visiting sequences for standard, non-binary, or custom traversal rules (e.g., Root-Right-Left).
Expression Tree Synthesis & Optimization
occasional · mixed · 2 marks · 2016, 2014
Constructing expression trees from postfix/infix expressions, evaluating expressions over binary leaf variables, or maximizing/minimizing target values.
Recursive Tree Code Analysis & Alternate Representations
occasional · MCQ · 2 marks · 2014, 2012
Analyzing or completing recursive pseudocode functions computing properties like tree height or counting leaves in alternate representations like the left-child right-sibling representation.
BFS / DFS Search Order & Level Properties
occasional · NAT · 1 marks · 2021, 2016
Determining node ordering, maximum vertex index at a given depth/distance, or comparing visited sets between BFS (level-order) and DFS.

Formulas GATE uses

Leaf vs Two-Child Nodes Identity

n_0 = n_2 + 1

Used in any binary tree to relate the number of leaf nodes ( $n_0$ ) to the number of internal nodes with two children ( $n_2$ ).

Strict / Full Binary Tree Node Count

n = 2n_2 + 1 \iff n_2 = \frac{n - 1}{2}

Used when every node in the binary tree has either 0 or 2 children ( $n_1 = 0$ ).

Maximum Nodes in Binary Tree of Height h

N_{\max} = 2^{h+1} - 1

Used when finding the maximum capacity of a binary tree where height $h$ is defined as the number of edges on the longest root-to-leaf path.

Minimum Nodes in Binary Tree of Height h

N_{\min} = h + 1

Used for degenerate / skewed binary trees where each level has exactly 1 node.

Max Nodes up to Distance / Level d (BFS Index Bound)

\sum_{k=0}^{d} 2^k = 2^{d+1} - 1

Used to find the maximum possible BFS visit index for a node at depth/distance $d$ from the root.

Edge-Degree Sum Relation

E = n - 1 = n_1 + 2n_2

Used to derive relationships between nodes of different degrees ( $0, 1, 2$ ) and total node count.

Examiner traps in Trees

Height definition confusion: GATE consistently defines height as the number of edges on the longest path (leaf height = 0, root-only tree height = 0), not number of nodes/levels.
Assuming binary tree traversal rules on general multi-way trees without properly applying leftmost-child -> root -> remaining-children definition.
LCRS representation misinterpretation: forgetting that in left-child right-sibling, a node is a leaf in the original tree if and only if its leftMostChild is NULL.
Parenthesization/operator associativity errors when converting postfix expression strings into binary expression trees.
Off-by-one errors in node counting when confusing total internal nodes (n1 + n2) with strictly degree-2 internal nodes (n2).

How questions are asked

Direct numerical computation of node counts or tree height (NAT)
Recursive pseudocode blank filling or return-value identification (MCQ)
Expression tree value maximization under binary variable constraints (NAT)
Reconstructing tree from traversal strings to evaluate structural metrics (NAT)
Tracing custom traversal rules or multi-way tree traversals (MCQ)
Matching standard traversal definitions to order of visit (MCQ)

Paper trends

Core structural counting relations ( $n_0 = n_2 + 1$ ) remain an enduring staple across decades, tested as direct NATs in 2015 and algebraic MCQs in 2025.
2025, 2015
Shift towards direct numerical answers (NAT) for height calculation from reconstructed trees and level-by-level BFS bounds.
2021, 2018, 2016
Traversals are tested beyond simple rote binary definitions, including general multi-way trees (2014) and custom recursive traversal strategies (2016).
2026, 2016, 2014

Difficulty notes

Easy questions test direct formula substitution ( $n_0 = n_2 + 1$ , maximum nodes $2^{h+1}-1$ , matching basic traversal definitions). Medium questions require multi-step execution: constructing an expression tree from postfix notation followed by a custom traversal, reconstructing a unique binary tree from inorder/postorder traversals to calculate path lengths, or analyzing recursive code handling LCRS multi-way tree pointers.