A binary tree is a hierarchy where every node has at most two children, and a binary search tree adds one ordering rule that turns it into a searchable structure. Be precise about what that buys you, because examiners are: a BST lookup costs O(h), where h is the height of the tree. That is O(log n) only while the tree stays balanced, and it degrades to O(n) in the worst case, when it does not. A BST built from already-sorted keys is a straight line. Balanced variants such as AVL and red-black trees are what turn the logarithmic cost into a guarantee. This pairing is one of the highest-yield topics across GATE, NET, and every placement round, because so much else (heaps, balanced trees, tries) builds on it. The good news is that almost every question reduces to a handful of definitions and four traversals.
Binary tree terminology
Fix these terms, because exam questions are often just definitions in disguise.
The root is the topmost node. A leaf is a node with no children. Every non-root node has exactly one parent.
The depth (or level) of a node is the number of edges from the root down to it, so the root is at depth 0. The height of a tree is the number of edges on the longest root-to-leaf path.
The degree of a node is its number of children (0, 1, or 2 in a binary tree).
A full binary tree has every node with either 0 or 2 children. A complete binary tree is filled level by level, left to right, with only the last level allowed to be partially filled. A perfect binary tree is the strictest of the three: every internal node has exactly two children and every leaf sits at the same depth, so a perfect tree is automatically both full and complete.
Two counting facts follow directly and are heavily tested: a perfect binary tree of height h has exactly 2^(h+1) − 1 nodes, of which 2^h are leaves. Turn that around and any binary tree holding n nodes has height at least ⌊log2(n)⌋, a floor reached only when every level except the last is full. That floor is why keeping trees short is the whole game.
The traversals: three depth-first, one breadth-first
A traversal visits every node once in a defined order. The three classic depth-first traversals are distinguished only by when you visit the node relative to its subtrees:
Inorder (Left, Node, Right): traverse left subtree, visit node, traverse right subtree.
Preorder (Node, Left, Right): visit node first, then both subtrees.
Postorder (Left, Right, Node): visit node last.
A fourth traversal, level-order (also called breadth-first), does not follow that pattern at all: it visits every node of one level, left to right, before moving to the next, and is written with a queue instead of recursion. When a textbook says "the three traversals" it means only the depth-first family. Hold on to that distinction, because level-order is the traversal placement interviews ask for most.
A worked traversal
Insert 50, 30, 70, 20, 40, 60, 80 into an empty binary search tree and you get this perfect tree of height 2 (seven nodes, every leaf at depth 2):
Now read off each traversal. The first three apply their rule recursively; the fourth simply sweeps the levels.
Inorder (L, N, R): 20, 30, 40, 50, 60, 70, 80.
Preorder (N, L, R): 50, 30, 20, 40, 70, 60, 80.
Postorder (L, R, N): 20, 40, 30, 60, 80, 70, 50.
Level-order (BFS): 50, 30, 70, 20, 40, 60, 80.
Notice the inorder result is sorted. That is not a coincidence and it is the single most useful property in this topic: an inorder traversal of a binary search tree always emits the keys in ascending order.
Binary search trees: the ordering rule
A binary search tree (BST) is a binary tree with one invariant: for every node, all keys in its left subtree are smaller, and all keys in its right subtree are larger. That single rule powers three operations.
Search. Start at the root, compare the target with the current key, go left if smaller and right if larger, and stop when you match or hit an empty spot. Searching for 60 in the tree above: 60 > 50 so go right to 70, 60 < 70 so go left to 60, found. Each comparison discards one subtree and moves you down exactly one level, so the cost is proportional to the height, O(h), never to the number of nodes. Only in a reasonably balanced tree does discarding a subtree throw away about half the remaining keys, and only then does O(h) collapse to O(log n).
Insert. Search for the key as above; wherever the search falls off the tree, attach the new node there. That is exactly how the seven nodes above were placed.
Delete. Three cases, and this is the one examiners probe:
Leaf node: just remove it.
One child: replace the node with its single child.
Two children: replace the node's key with its inorder successor (the smallest key in its right subtree), then delete that successor from the right subtree. Deleting 30 above: its inorder successor is 40, so 40 moves up into 30's place and the old 40 leaf is removed. The BST ordering is preserved.
Why balance matters: the AVL intuition
Every BST operation costs time proportional to the tree's height, not its node count. Insert keys in sorted order (10, 20, 30, ...) and the tree degenerates into a straight line of height n − 1, so search becomes O(n), no better than a linked list. A self-balancing tree such as an AVL tree prevents this by requiring, at every node, that the heights of the left and right subtrees differ by at most one (a balance factor in {−1, 0, +1}). When an insertion or deletion breaks that condition, the tree performs rotations to restore it, guaranteeing the height stays O(log n) and therefore that every operation stays logarithmic. A red-black tree makes the same O(log n) promise through a looser colouring invariant, which is why it backs most standard-library ordered maps. That guarantee, not the ordering rule on its own, is the entire reason balanced trees exist.
Keep the whole cost picture straight: search, insert and delete are each O(h) (O(log n) in a balanced tree, O(n) in a degenerate one), while a traversal has to touch every node, so it is Θ(n) time whatever the tree's shape. The recursive traversals also carry O(h) stack space, and level-order carries a queue that can hold an entire level, O(n) in the worst case. Storing the tree itself is O(n) either way.
Tree questions in GATE, UGC NET and placements
GATE CS tests trees constantly. Expect "reconstruct the tree from its inorder and preorder", "count the number of binary trees / BSTs with n nodes" (the Catalan-number result), traversal outputs, and BST operation traces. Height and node-count bounds appear as quick numericals. Our GATE CS exam category sequences trees with heaps and graphs.
UGC NET Computer Science favours definitions and traversal outputs: full versus complete versus perfect, the inorder-gives-sorted property, and AVL balance factors. Precise terms score.
Placement and company tests are where trees are unavoidable: level-order traversal, height of a tree, lowest common ancestor, validating a BST, and balanced-tree checks are staple interview questions. Drill them on the placement preparation category.
KnowledgeGate's question bank carries over 1,400 Data Structures questions, and trees are among its densest sub-areas, so there is ample practice on exactly these patterns.
Practise it, do not just read it
Trees are learned by drawing them and tracing operations by hand, not by rereading definitions.
Work the full topic with solved traversals and operations on the Data Structures Tree learn module.
For GATE-depth Data Structures across the whole syllabus, GATE Guidance by Sanchit Sir sequences trees with sorting, hashing, and graphs.
To see where trees sit in the wider prep plan, our GATE preparation guide maps the full subject order.
Learn the vocabulary, run all four traversals on one small tree, trace a two-child deletion, and remember that height is what every cost depends on. Do that, and trees become marks you can count on.
Ready to test yourself? Work through our solved trees and BST MCQs, each answered in a couple of lines, to see exactly how these ideas are examined.
