GATE CSE Trees PYQs
In GATE CS, the 'Trees' topic tests structural counting relations in binary trees, tree traversal techniques (standard, custom, and multi-way tree traversals),… Read the guide
- Questions
- 13
- Asked
- since 2012
- Total marks
- 17
- Marks / paper
- 0.7
13 GATE CSE Trees PYQs with solutions, from Programming and Data Structures. Browse all GATE CSE PYQs.
Questions
Every official paper that asked this topic, newest first.
- GATE CSE 2026 Set 2 · Q12The set represents various traversals over binary tree. The set represents the order of visiting nodes during a traversal. Which one of the following is the correct match from to ?MCQ1 markEasyDiagramSolve
- GATE CSE 2025 Set 2 · Q13Consider a binary tree in which every node has either zero or two children. Let be the number of nodes in . Which ONE of the following is the number of nodes in that have exactly two children?MCQ1 markEasySolve
- GATE CSE 2021 Set 2 · Q16Consider a complete binary tree with 7 nodes. Let denote the set of first 3 elements obtained by performing Breadth-First Search (BFS) starting from the root. Let denote the set of first 3 elements obtained by performing Depth-First Search (DFS) starting from the root. The value of is ________.NAT1 markEasySolve
- GATE CSE 2018 · Q20The 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 ________.NAT1 markMediumSolve
- GATE CSE 2016 Set 2 · Q11Breadth First Search (BFS) is started on a binary tree beginning from the root vertex. There is a vertex at a distance four from the root. If is the -th vertex in this BFS traversal, then the maximum possible value of is _________.NAT1 markEasySolve
- GATE CSE 2016 Set 2 · Q36Consider the following strategy for traversing a binary tree:
• Visit the root;• Visit the right subtree using ; • Visit the left subtree using ; The traversal of the expression tree corresponding to the reverse polish expression3 4 * 5 - 2 ^ 6 7 * 1 + -…MCQ2 marksMediumSolve - GATE CSE 2015 Set 1 · Q25The 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 areMCQ1 markEasySolve
- GATE CSE 2015 Set 2 · Q10A binary tree T has 20 leaves. The number of nodes in T having two children is ______.NAT1 markEasySolve
- GATE CSE 2015 Set 3 · Q25Consider a binary tree T that has 200 leaf nodes. Then, the number of nodes in T that have exactly two children are _____.NAT1 markEasySolve
- GATE CSE 2014 Set 2 · Q39Consider 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 _____.NAT2 marksMediumDiagramSolve
- GATE CSE 2014 Set 3 · Q12Consider 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 isMCQ1 markMediumDiagramSolve
- GATE CSE 2014 Set 3 · Q41Consider 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 typetreeNode.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); }…MCQ2 marksMediumSolve - GATE CSE 2012 · Q47The 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 pointerroot.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 } } }…MCQ2 marksEasySolve
What GATE tests in Trees
Concepts, patterns, formulas and traps distilled from past papers.
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
Commonmixed1 marks2025, 2015Using handshaking/edge-node relations (, for strictly binary trees, or min/max nodes given height ) to find counts of leaves, full nodes, or total nodes.
Tree Reconstruction & Traversal Order Evaluation
Commonmixed1.5 marks2026, 2018, 2016, 2014Reconstructing 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
Occasionalmixed2 marks2016, 2014Constructing expression trees from postfix/infix expressions, evaluating expressions over binary leaf variables, or maximizing/minimizing target values.
Recursive Tree Code Analysis & Alternate Representations
OccasionalMCQ2 marks2014, 2012Analyzing 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
OccasionalNAT1 marks2021, 2016Determining 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
Used in any binary tree to relate the number of leaf nodes () to the number of internal nodes with two children ().
Strict / Full Binary Tree Node Count
Used when every node in the binary tree has either 0 or 2 children ().
Maximum Nodes in Binary Tree of Height h
Used when finding the maximum capacity of a binary tree where height is defined as the number of edges on the longest root-to-leaf path.
Minimum Nodes in Binary Tree of Height h
Used for degenerate / skewed binary trees where each level has exactly 1 node.
Max Nodes up to Distance / Level d (BFS Index Bound)
Used to find the maximum possible BFS visit index for a node at depth/distance from the root.
Edge-Degree Sum Relation
Used to derive relationships between nodes of different degrees () 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 () 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 (, maximum nodes , 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.