Trees and binary search trees

In short

A tree is a hierarchical, acyclic data structure of nodes in which every node except the root has exactly one parent; a binary tree restricts each node to at most two children, and a binary search tree (BST) adds the ordering rule that everything in the left subtree is smaller and everything in the right subtree is larger than the node's key. This ordering gives search, insert and delete in O(h) time, which is O(log n) when the tree is shaped well and O(n) when it degenerates into a list. Trees are compulsory in every Indian CS syllabus (AICTE model curriculum, UGC CBCS data structures course) and appear in GATE CS every year as traversals, height/node counting, Catalan counting and BST operations. In placements they are the backbone of tree rounds at TCS NQT, Infosys, Wipro, Accenture and of the hard rounds at Amazon, Microsoft, Google, Flipkart, Zoho, Adobe and Oracle India.

Explained

Terminology and basic properties

• Node, edge, root, leaf: the root has no parent; a leaf (external/terminal node) has no children; all others are internal nodes.
• Degree of a node = number of its children; degree of the tree = maximum node degree. A binary tree has degree ≤ 2.
• Level: root is at level 0 (some books use 1 — state your convention). Depth of a node = number of edges from root to it. Height of a node = edges on the longest path down to a leaf; height of the tree = height of the root. A single node has height 0 (edge convention) or 1 (node convention).
• Ancestor, descendant, sibling, subtree, forest (a disjoint set of trees), path length, internal path length (sum of depths of all nodes).
• A tree with n nodes has exactly n − 1 edges; there is exactly one path between any two nodes.
• A binary tree with n nodes has exactly n + 1 NULL (empty) child pointers — the basis of threaded trees.
• Relation between leaves and 2-degree nodes: n₀ = n₂ + 1, where n₀ = leaves and n₂ = nodes with two children (independent of n₁).

Types of binary trees

• Full (strict/proper): every node has 0 or 2 children. Then n is odd and leaves = (n + 1)/2.
• Perfect: all internal nodes have two children and all leaves are at the same level; n = 2^h+1 − 1.
• Complete: all levels filled except possibly the last, which is filled left to right — the shape used for array storage and for heaps. Almost complete is another name for this shape.
• Height-balanced: heights of left and right subtrees of every node differ by at most 1 (the AVL condition). Every complete tree is height-balanced, but not the reverse; the self-balancing schemes are a separate topic.
• Skewed (degenerate): every node has at most one child — left-skewed or right-skewed; behaves like a linked list, h = n − 1.
• Binary search tree: key-ordered binary tree, left subtree keys < node key < right subtree keys (for distinct keys). Duplicates must be handled by a stated rule — reject, keep a count field, or always go right.
• Expression tree: operators at internal nodes, operands at leaves; inorder gives infix, preorder gives prefix, postorder gives postfix.
• Threaded binary tree: NULL right pointers store the inorder successor (single-threaded) and NULL left pointers the inorder predecessor (double-threaded), allowing traversal without recursion or a stack; a boolean flag per pointer tells thread from child.
• General (k-ary) tree: converted to a binary tree by the left-child right-sibling representation.

Representation in memory

• Linked representation: struct node { int data; node *left, *right; }; — the standard; wastes one pointer per empty child but handles any shape.
• Array (sequential) representation, root at index 0: left child of i = 2i + 1, right child = 2i + 2, parent = ⌊(i − 1)/2⌋. With 1-based indexing: 2i, 2i + 1, ⌊i/2⌋.
• Array form is compact for a complete tree but needs 2^h+1 − 1 slots for a skewed tree of n nodes — exponentially wasteful.
• Common augmentations: a parent pointer (for successor queries without a stack), a subtree size field (order statistics: kth smallest, rank), a height field (balancing).

Traversals

Depth-first traversals, each O(n) time; auxiliary space O(h) for the recursion stack (O(n) worst case, O(log n) balanced):

1. Inorder (LNR): left, node, right. On a BST this outputs keys in ascending order — the most used property in exams.
2. Preorder (NLR): node, left, right. Used to copy/serialise a tree; prefix form of an expression.
3. Postorder (LRN): left, right, node. Used to delete/free a tree, compute heights and sizes bottom-up; postfix expression.
4. Level order (BFS): level by level, using a queue; O(n) time, O(w) space where w is the maximum width.
5. Iterative versions: inorder and preorder with an explicit stack; postorder with two stacks or one stack plus a "last visited" pointer.
6. Morris traversal: inorder in O(n) time and O(1) extra space by temporarily threading the rightmost node of the left subtree back to the current node, then undoing it.
7. Reconstruction: inorder + preorder, or inorder + postorder, determine a binary tree uniquely (keys distinct). Preorder + postorder do not — they cannot tell a single left child from a single right child, but they do determine a full binary tree uniquely. For a BST, preorder alone (or postorder alone, or level order alone) is enough, because sorting it gives the inorder.

BST operations

• Search(k): compare with root; go left if smaller, right if larger; stop on match or NULL. O(h) comparisons.
• Insert(k): search for k; attach the new node at the NULL position reached. Every insertion creates a leaf. O(h).
• Delete(k) — three cases:
  1. Leaf: remove it, set the parent's pointer to NULL.
  2. One child: splice the node out — the child takes its place.
  3. Two children: replace the key with its inorder successor (leftmost node of the right subtree) or inorder predecessor (rightmost of the left subtree), then delete that node recursively — it has at most one child.
• Minimum / maximum: leftmost / rightmost node, O(h).
• Inorder successor: if a right subtree exists, its minimum; otherwise the lowest ancestor whose left subtree contains the node.
• Floor / ceiling, range search, kth smallest (with subtree sizes), LCA of two keys (walk down from the root; the first node whose key lies between the two is the LCA — O(h) in a BST, against O(n) in a plain binary tree).
• Validation: a correct isBST check passes down a (min, max) range, or verifies that the inorder traversal is strictly increasing. Comparing only a node with its two children is the classic wrong answer.
• Sorting: inserting n keys then an inorder walk is tree sort — O(n log n) average, O(n²) if the input is already sorted (skewed tree).
• Hibbard deletion (always taking the successor) biases the tree; after many random insert/delete pairs the average search cost degrades towards Θ(√n), which is one reason production libraries use balanced trees.

Complexity, shape and counting

• Every BST operation costs O(h). With n nodes, h ranges from ⌊log₂ n⌋ (balanced) to n − 1 (skewed).
• Random insertion order gives an expected successful-search cost of ≈ 1.39 log₂ n comparisons (average node depth ≈ 2 ln n); the expected *height* is larger, ≈ 3 log₂ n. Sorted input gives the worst case, which is precisely why AVL / red-black trees exist.
• The number of distinct binary tree shapes with n nodes, and equally the number of distinct BSTs on n given distinct keys, is the nth Catalan number Cₙ. The number of distinct labelled binary trees on n nodes is Cₙ × n!.
• BST vs hash table: a hash table gives O(1) average lookup but no order; a BST gives O(log n) lookup plus sorted traversal, range queries, successor/predecessor, floor/ceiling.
• Practical note: Java's TreeMap/TreeSet and C++ std::map/std::set are ordered trees (red-black), HashMap/unordered_map are hash tables; database and file-system indexes use B/B+ trees because of disk-block sizes — those are covered in their own notes.

/* Iterative BST search and insert */
node* search(node *r, int k){
    while (r && r->data != k) r = (k < r->data) ? r->left : r->right;
    return r;                      /* NULL if absent */
}
node* insert(node *r, int k){      /* recursive; returns new subtree root */
    if (!r) return newnode(k);
    if (k < r->data) r->left  = insert(r->left,  k);
    else if (k > r->data) r->right = insert(r->right, k);
    return r;                      /* duplicate ignored */
}
int height(node *r){               /* edges; empty tree = -1 */
    if (!r) return -1;
    int l = height(r->left), rt = height(r->right);
    return 1 + (l > rt ? l : rt);
}
int isBST(node *r, int lo, int hi){
    if (!r) return 1;
    if (r->data <= lo || r->data >= hi) return 0;
    return isBST(r->left, lo, r->data) && isBST(r->right, r->data, hi);
}

Key points

• Tree - acyclic hierarchical structure; n nodes always have n − 1 edges and one unique path between any two nodes.
• Binary tree - at most two children per node; n nodes leave n + 1 NULL links.
• Height convention - edges on the longest root-to-leaf path; empty tree = −1, single node = 0. Declare it in the exam.
• Max nodes - 2^l at level l; 2^h+1 − 1 in a tree of height h; minimum nodes at height h is h + 1.
• Min height - ⌊log₂ n⌋ for n nodes; max height n − 1 (skewed).
• n₀ = n₂ + 1 - leaves exceed two-child nodes by exactly one in any binary tree.
• Complete tree in an array - children of i at 2i+1, 2i+2; parent at ⌊(i−1)/2⌋ (0-based).
• Inorder of a BST is sorted - the single most used fact about BSTs.
• Traversal cost - all four are O(n) time; DFS uses O(h) stack, BFS uses O(w) queue.
• Unique reconstruction - inorder with preorder, or inorder with postorder; preorder+postorder only for full binary trees; any one traversal suffices for a BST.
• BST search/insert/delete - O(h): O(log n) balanced, O(n) skewed.
• Deletion with two children - replace by inorder successor (or predecessor), then delete that node.
• Insertion always creates a leaf - the BST shape depends entirely on insertion order.
• Catalan number - Cₙ distinct BSTs on n distinct keys (1, 1, 2, 5, 14, 42 for n = 0…5).
• Threaded tree - reuses NULL pointers as inorder links for stack-free traversal.
• Morris traversal - inorder in O(1) extra space using temporary threads.
• Augment with subtree size - gives kth smallest and rank in O(h).
• Sorted input is the worst input - it produces a skewed BST, the reason balanced variants exist.

Formulas and examples

Example 1 — Build a BST and traverse it. Insert 50, 30, 70, 20, 40, 60, 80 in that order.

• 50 is the root; 30 < 50 → left; 70 > 50 → right; 20 < 30 → left of 30; 40 > 30 → right of 30; 60 < 70 → left of 70; 80 > 70 → right of 70.
• Shape: a perfect tree, n = 7, h = 2, leaves = 4 = (7+1)/2. ✓
• Inorder: 20, 30, 40, 50, 60, 70, 80 (sorted ✓). Preorder: 50, 30, 20, 40, 70, 60, 80. Postorder: 20, 40, 30, 60, 80, 70, 50. Level order: 50, 30, 70, 20, 40, 60, 80.
• Internal path length = 0 + 1 + 1 + 2 + 2 + 2 + 2 = 10 → average successful search = 10/7 + 1 ≈ 2.43 comparisons.
• Now insert the same keys in sorted order 20, 30, 40, 50, 60, 70, 80: a right-skewed tree, h = 6, average search = (1+2+3+4+5+6+7)/7 = 4 comparisons — 65% worse for identical data.

Example 2 — Deletion, all three cases, on the tree of Example 1.

• Delete 20 (leaf): remove it; 30's left becomes NULL.
• Delete 30 (now one child, 40): splice out — 50's left pointer now points to 40.
• Delete 50 (two children): inorder successor = minimum of the right subtree {70, 60, 80} = 60. Copy 60 into the root and delete the old 60 (a leaf). Result inorder: 40, 60, 70, 80 — still sorted ✓.

Example 3 — Reconstruct a tree from two traversals. Preorder = A B D E C F, Inorder = D B E A C F.

• Preorder's first element A is the root. In the inorder, D B E lie left of A and C F right → left subtree {D, B, E}, right subtree {C, F}.
• Next 3 preorder items B D E build the left subtree: root B, inorder D B E → D is the left child, E the right child.
• Remaining preorder C F build the right subtree: root C; inorder C F → F lies right of C, so F is C's right child.
• Postorder = D E B F C A; height = 2; leaves = D, E, F (3), two-child nodes = A, B (2) → n₀ = n₂ + 1 ✓.

Example 4 — Counting. How many distinct BSTs can be made with the keys {1, 2, 3, 4}?

• C₄ = C(8,4)/(4+1) = 70/5 = 14. (C₃ = 20/4 = 5, C₅ = 252/6 = 42.)
• Check by root: root 1 → C₀ × C₃ = 1 × 5 = 5; root 2 → C₁ × C₂ = 1 × 2 = 2; root 3 → C₂ × C₁ = 2; root 4 → C₃ × C₀ = 5. Total 5 + 2 + 2 + 5 = 14 ✓.
• The number of distinct binary tree *shapes* with 4 nodes is also 14; the number of *labelled* binary trees on 4 nodes is 14 × 4! = 336.

Example 5 — Counting nodes and height. A binary tree has 20 nodes of degree 2 and 10 nodes of degree 1.

• Leaves n₀ = n₂ + 1 = 21; total nodes n = 21 + 10 + 20 = 51; edges = 50; NULL pointers = 52.
• A BST holding 10,00,000 (10 lakh) records: minimum height = ⌊log₂ 10⁶⌋ = 19 (2¹⁹ = 5,24,288; 2²⁰ = 10,48,576), so about 20 comparisons when balanced, against 10,00,000 in the skewed worst case.

Where it is used

• Product-company interviews (Amazon, Microsoft, Google, Adobe, Flipkart, Swiggy, Zoho, Walmart Global Tech India): tree questions are a standing round — LCA, diameter, views, serialise/deserialise, BST validation, kth smallest.
• Language libraries and backend code: C++ std::map/std::set, Java TreeMap/TreeSet, Python's sortedcontainers — ordered dictionaries, leaderboards, range filters in e-commerce and fintech services.
• Databases and file systems: index structures and directory hierarchies in MySQL, PostgreSQL, MongoDB and ext4/NTFS are tree-based (B/B+ tree variants — separate topic), but the search-tree logic is the same.
• Compilers and interpreters: parse trees and abstract syntax trees; expression trees inside spreadsheet and rules engines; XML/JSON/DOM structures in web apps.
• Networking and systems roles: routing tables, IP longest-prefix structures, decision trees in ML pipelines, scene/BVH trees in graphics and game studios (Ubisoft Pune, Rockstar India).
• Exams and recruitment tests in India: GATE CS (traversal, counting, BST property questions every year), ISRO/BARC/DRDO scientist papers, UGC-NET Computer Science, and the coding rounds of TCS NQT, Infosys HackWithInfy, Wipro NTH and Capgemini.

Interview questions

• Q: What makes a binary tree a binary search tree? A: For every node, all keys in its left subtree are smaller and all keys in its right subtree are larger — the condition must hold for the whole subtree, not just the immediate children.
• Q: Which traversal of a BST gives sorted order, and why? A: Inorder — it visits the entire left subtree (all smaller keys) before the node and the right subtree (all larger keys) after it.
• Q: How do you check whether a binary tree is a BST? A: Recurse with a valid (min, max) range for each node, or do an inorder traversal and confirm it is strictly increasing; both are O(n).
• Q: Why is BST search O(log n) only sometimes? A: Cost is O(h); a balanced tree has h ≈ log₂ n, but insertion in sorted order produces a skewed tree with h = n − 1, making search O(n).
• Q: How do you delete a node with two children? A: Replace its key with the inorder successor (minimum of the right subtree) or the inorder predecessor, then delete that node, which has at most one child.
• Q: Can a binary tree be rebuilt from its preorder and postorder traversals? A: Not in general — a node with a single child is ambiguous; it works only for full binary trees, or if the tree is a BST.
• Q: How many distinct BSTs can be built from n distinct keys? A: The nth Catalan number, (2n)!/(n!(n+1)!) — 5 for n = 3, 14 for n = 4.
• Q: Find the lowest common ancestor of two keys in a BST. A: Walk down from the root; while both keys are smaller go left, while both are larger go right; the first node that lies between them (or equals one of them) is the LCA — O(h).
• Q: How would you find the kth smallest element in a BST? A: Store a subtree-size field in each node and descend using it, giving O(h); without augmentation, do an inorder traversal and stop at the kth node, O(k) up to O(n).
• Q: How do you do an inorder traversal in O(1) extra space? A: Morris traversal — temporarily link the rightmost node of the left subtree to the current node, traverse, then restore the NULL.
• Q: When would you prefer a hash table over a BST? A: When only exact-match lookups are needed and order is irrelevant — hashing gives O(1) average; a BST is preferred for sorted traversal, range, successor, floor and ceiling queries.
• Q: A binary tree has 15 nodes of degree 2 and 4 of degree 1. How many leaves and nodes in all? A: Leaves = 15 + 1 = 16; total = 16 + 4 + 15 = 35.

Common mistakes

• Checking only each node against its two children when validating a BST — it wrongly accepts trees where a deep node violates an ancestor's range.
• Mixing the two height conventions mid-answer (edges vs nodes), which puts every count off by one; declare the convention first.
• Confusing full, complete and perfect binary trees, and quoting 2^h+1 − 1 nodes for a tree that is merely complete.
• Assuming preorder plus postorder rebuilds any binary tree, or that one traversal of a general binary tree is enough.
• Forgetting the base case or the empty tree in recursive code, and returning 0 instead of −1 for the height of an empty tree.
• Deleting a two-child node by removing it outright instead of promoting the inorder successor, which breaks the BST property.
• Claiming BST operations are O(log n) without the balance caveat — an interviewer will immediately ask about sorted insertion.

Related topics

Balanced trees: AVL, red-black and B-trees · Heaps and priority queues · Hashing and hash tables · Tries and string data structures · Graphs and their representation · Recursion and divide-and-conquer