Chapter 11 — Data structures – Binary trees [ Conceptual ]

Introduction and basic idea
A binary tree is a hierarchical data structure consisting of nodes where each node may have at most two children. These children are conventionally called the left child and the right child. The topmost node is the root; every other node can be reached by following child links from the root. Binary trees model natural hierarchies and branching processes and are central to many algorithms because they let us split problems into two smaller subproblems.

Node contents and pointers
Each node typically stores a data item (for example a key or value) and two references or pointers to its left and right children. When a child does not exist the pointer contains NULL (or a sentinel). Implementations vary: in pointer-based languages each node is an object or struct with fields for data and child pointers; in array-based implementations indexes are used for parents and children if the tree is complete.

Empty tree and single node tree
An empty tree has no nodes and is often represented by a NULL root pointer; many recursive algorithms treat the empty tree as the base case. A single-node tree has a root which is also a leaf. These simple cases are important when writing correct recursive functions because they provide termination conditions and simple behaviours to reason about.

Why binary trees are useful
Binary trees are useful because of their recursive structure: every subtree is itself a binary tree. This self-similarity allows straightforward recursive algorithms for traversals, searching, insertion and deletion. Binary trees are versatile: they can be shaped to optimise different operations — for example search performance in Binary Search Trees or priority handling in heaps.

Key metrics
Two common measures help evaluate algorithms on trees: depth (distance from root) and height (longest path from a node to a leaf). The height of the tree affects operation costs: many tree algorithms run in time proportional to the height, so controlling height is central to performance. A perfectly balanced tree minimises height for a given number of nodes, while skewed trees maximise it.

Applications
Binary trees appear in expression parsing (expression trees), file-system-like directory representations, decision processes, game trees, and as internal structures for search indexes. Learning binary trees gives students a basis for understanding more advanced balanced trees and graph algorithms.

Overview of key terms
To work with binary trees it is important to know the standard vocabulary. A node is a unit containing data and references to children. The root is the unique top node with no parent. Children are nodes directly connected below a node. A parent is the node directly above. Siblings are nodes that share the same parent. Leaves (or external nodes) are nodes with no children. Internal nodes have at least one child.

Degree, path, ancestor and descendant
The degree of a node is the number of children it has: 0, 1 or 2 in a binary tree. A path is a sequence of nodes connected by edges; path length is the number of edges on that path. Ancestors of a node are nodes on the path from the root down to its parent; descendants are nodes that follow it downwards. These terms help describe locations and relationships inside a tree very precisely.

Subtree and forest
A subtree rooted at node X is the node X together with all its descendants. Any subtree is itself a binary tree and can be manipulated independently in algorithms. A forest is a collection of trees; for example, deleting a root can produce a forest of its child subtrees. Recognising subtrees is useful when designing divide-and-conquer algorithms.

Depth, level and height
Depth of a node equals the number of edges from the root to the node. When levels are counted starting from 1, level = depth + 1. Height of a node is the number of edges on the longest path from that node down to a leaf; height of the tree is the height of its root. Different texts sometimes count edges or nodes; when answering exam questions clearly state which convention you follow (ICSE usually expects height measured in edges).

External/internal distinction and null pointers
Leaves are external nodes; internal nodes have children and are often the focus of updates. A missing child pointer is typically NULL; many algorithms treat NULL as the base case for recursion. When visually representing trees, drawing NULL children helps avoid ambiguity about whether a node is missing or deliberately omitted.

Why precise terminology matters
Clear use of these terms makes it easier to describe algorithms and prove correctness. In exam answers and code comments use consistent definitions, label diagrams with depth/height values if asked, and explain any assumptions such as how duplicate keys are handled in search trees.

Introduction to common types
Binary trees can take several special shapes that have specific properties and uses. Being able to recognise and reason about these types is important for both theory and implementation. The main types students meet are full (strict), perfect, complete, skewed and balanced trees. Each type imposes structural constraints that affect performance and storage.

Full (strict) binary tree
A full binary tree is one where every node has either 0 or 2 children. In a full tree you never find a node with exactly one child. This structure simplifies some induction proofs and counting arguments, for example relating internal nodes to leaves because internal nodes always pair up with two children.

Perfect binary tree
A perfect binary tree is a full tree where all leaves are at the same level. It is completely filled: every level from the root to the leaves contains the maximum possible number of nodes. A perfect tree of height h (counting edges) has exactly 2^{h+1} - 1 nodes. Perfect trees are theoretical ideals used in examples and provide best-case heights for fixed node counts.

Complete binary tree
A complete binary tree is filled level by level from left to right; all levels except possibly the last are full, and the last level has nodes pushed to the left with no gaps between them. This property is why arrays are ideal to store heaps: node positions map to array indices with no unused holes except possibly at the end.

Skewed trees
A left-skewed or right-skewed tree has nodes each with only one child, all arranged on the same side. Skewed trees behave like linked lists: their height is O(n) and operations that depend on height degrade to linear time. Skewness can occur in BSTs when keys are inserted in sorted order.

Balanced trees (conceptual)
Balanced trees keep heights of subtrees roughly equal to maintain logarithmic height. Different precise definitions exist: AVL trees require height difference ≤ 1 at each node, Red-Black trees impose colour rules that bound height. Conceptually, balance avoids long chains and ensures good performance for search and update operations.

Why identifying types matters
The type determines expected complexity and storage layout. For instance heaps need completeness, BSTs benefit from balance, and skewed trees warn about worst-case behaviour. When solving problems, state the tree type clearly and use its properties for counting nodes, proving bounds and designing algorithms.

What traversal means
Traversal of a tree is the process of visiting every node exactly once in a systematic order. Different traversal orders are useful for different tasks. Broadly, traversals are divided into depth-first traversals (preorder, inorder, postorder) and breadth-first traversal (level-order). Understanding their differences and use-cases is essential for algorithm design and for answering many exam-style questions.

Depth-first traversals
Depth-first traversals explore as far as possible along each branch before backtracking. Preorder visits the current node before its subtrees (root, left, right). Inorder visits the left subtree, then the node, then the right subtree (left, root, right). Postorder visits the node after its subtrees (left, right, root). These are naturally expressed recursively because each subtree is processed by the same method.

When to use each depth-first order
Inorder traversal is special for Binary Search Trees because it returns node keys in sorted (ascending) order — a key property used in both algorithms and proofs. Preorder is helpful for creating a copy of the tree or serialising structure because it records roots before children. Postorder is commonly used to delete nodes or to evaluate expression trees because children must be processed before a parent operation.

Level-order (breadth-first)
Level-order visits nodes level by level from top to bottom and left to right within levels. It is implemented using a queue: enqueue the root, then repeatedly dequeue a node, visit it, and enqueue its children. Level-order is useful when operations depend on node depth or when building complete trees. It is also the basis for breadth-first search (BFS) in graphs.

Complexity and resource use
All these traversals visit each node once and perform constant work per visit, so they are O(n) time. Space requirements vary: depth-first recursion uses O(h) stack space where h is tree height; level-order needs O(maximum width) queue space, which in balanced trees is O(n) in the worst case for the bottom level but typically O(n/2) at most.

Practical advice
Practice by tracing each order on small trees to build intuition. When asked to produce traversal sequences in exams, simulate the chosen order carefully and write each visited node in sequence. For implementation, choose recursion for clarity and iterative approaches with explicit stacks/queues for environments with limited recursion depth.

Recursive structure and base case
Recursion fits tree traversals because each subtree is itself a tree. A correct recursive traversal follows a base case and a recursive case. The base case is often when the current node reference is NULL: do nothing and return. The recursive case applies the traversal order to the current node and its subtrees. This structure leads to concise and easy-to-read algorithms.

Preorder, inorder and postorder pseudocode patterns
Preorder: if node is NULL return; visit(node); recurse(left); recurse(right). Inorder: if node is NULL return; recurse(left); visit(node); recurse(right). Postorder: if node is NULL return; recurse(left); recurse(right); visit(node). These patterns differ only in where the visit happens, and each can be implemented in a few lines of code in most languages.

Correctness by induction
Correctness of recursive traversals can be shown by induction on the number of nodes. For the base case of an empty tree the traversal produces an empty sequence. For a non-empty tree, assume the traversal correctly visits subtrees and then combine the results following the traversal order; the combination yields the complete visited sequence. This reasoning is useful in proofs and in exam answers.

Iterative implementations
Recursion uses the call stack implicitly. Iterative versions use explicit stacks. For inorder iterative traversal, push nodes while moving to leftmost children, then pop and visit, then move to right child. Postorder iterative traversal is trickier; common techniques include using two stacks or modifying the single-stack approach with node state flags. Iterative methods help in languages or environments where deep recursion causes stack overflow.

Space and time complexity
All standard traversals visit n nodes performing O(1) work per node, so time complexity is O(n). Recursive space is O(h) call stack frames where h is tree height; iterative stack or queue space has similar bounds. For skewed trees this can reach O(n), while balanced trees typically use O(log n) space.

Practical tips
When writing code include the base case explicitly. When tracing by hand, write the call stack or mark visited nodes to avoid confusion. Use postorder when operations depend on results from children, such as freeing memory or evaluating expressions.

BST property defined
A Binary Search Tree (BST) is a binary tree in which every node's left subtree contains keys less than the node's key and the right subtree contains keys greater than the node's key. This invariant must hold for every node in the tree. For duplicate keys a consistent rule is required (for example, equal keys go to the right); always state that convention when solving exam problems.

Why ordering helps
The BST property allows efficient searching by comparing the target key with the current node: if smaller go left, if larger go right. Each comparison narrows the search to one subtree, cutting down possibilities. In ideal balanced trees this yields logarithmic time behaviour; even in average random insertions a BST performs well.

Inorder gives sorted sequence
One key property of BSTs is that an inorder traversal outputs the keys in ascending order. This follows because inorder recursively visits left subtree (all smaller keys), then the root, then the right subtree (all larger keys). This property is widely used for retrieving sorted data from a dynamic set implemented as a BST.

Maintaining invariants
Every operation on a BST must preserve its ordering invariant. Insert places a new key at the leaf position determined by comparisons. Delete must remove a node while ensuring the BST property remains for all nodes; common deletion procedures use the inorder successor or predecessor to replace a deleted node with two children. Rotations and rebalancing operations used in balanced trees also preserve the inorder sequence.

Limitations and practicalities
BST performance depends on tree shape. Insertions in ascending order can make a BST skewed and degrade operations to O(n). Self-balancing variants (AVL, Red-Black) exist to provide worst-case guarantees but add bookkeeping. For smaller datasets or when input is random, simple BSTs are easy and efficient to implement.

When to choose BST
Use BSTs when you need dynamic ordered sets with efficient insert/delete and ability to retrieve sorted order. They are also a foundation for more advanced balanced tree structures and for teaching recursive data structure algorithms.

Search algorithm step-by-step
Searching for key K in a BST begins at the root. Compare K with the current node's key. If equal, the search succeeds. If K is smaller, follow the left child; if larger, follow the right child. Repeat until you either find the key or reach a NULL pointer (indicating the key is not present). This simple comparison-guided descent is what makes BST search efficient in balanced trees.

Insertion process
Insertion uses the same descent as search to find the appropriate place for the new key. Starting at the root, compare the key and follow left or right until reaching a NULL child; create a new node and attach it there. This operation preserves the BST invariant: the position chosen ensures that all nodes in left subtree are smaller and in right subtree are larger.

Recursive and iterative forms
Recursive insertion returns a pointer to the (possibly new) subtree root: if current node is NULL create and return new node; otherwise if key < node.key set node.left = insert(node.left, key) else set node.right = insert(node.right, key); return node. Iterative insertion follows parent pointers down to the insertion spot and then links the new node. Recursive code is shorter; iterative code avoids call stack overhead and may be preferred in constrained environments.

Handling duplicates
Decide how to treat duplicate keys: ignore duplicates, store a count in the node, or consistently place duplicates to one side. Document the convention in answers and keep it consistent in code and diagrams. Many exam questions assume unique keys unless duplicates are explicitly mentioned.

Complexity analysis
Time complexity of search and insert is O(h) where h is the tree height. For balanced trees h = O(log n), giving logarithmic time. For skewed trees h = O(n) and operations degrade to linear time. Space complexity for recursive insert uses O(h) call stack; iterative insert uses O(1) extra space beyond the tree nodes.

Practical tips and correctness
After insertions, a quick inorder traversal verifies the BST property by producing a sorted list. Maintain parent pointers if subsequent deletion or balancing requires easy access to parents; otherwise they can be omitted to save space.

Overview of deletion cases
Deleting a node from a BST must preserve the ordering invariant and so requires careful handling. There are three cases: (1) the node is a leaf; (2) the node has one child; (3) the node has two children. Each case has a straightforward, local solution that maintains the BST property.

Case 1: deleting a leaf
If the node is a leaf, simply remove it and set its parent's corresponding child pointer to NULL. If the node to delete is the root and also a leaf, the tree becomes empty. This is the simplest case and can be performed in O(1) time once the node is located.

Case 2: deleting a node with one child
Replace the node with its single child by adjusting the parent pointer to point to that child. This effectively removes the node while keeping the child subtree intact and preserves the BST order because the child subtree already has keys either all less than or all greater than the node's key according to which side it lies on.

Case 3: deleting a node with two children
This is the non-trivial case. The common method uses the node's inorder successor (the minimum node in its right subtree) or inorder predecessor (maximum in left subtree). Copy the successor's key into the node to be deleted, then delete the successor node, which will have at most one child and therefore fall into case 1 or 2. Using the successor keeps the inorder sequence intact and therefore preserves the BST property.

Algorithmic steps and helpers
Implement a helper function findMin(node) that returns the leftmost node of a subtree. Another helper transplant(u, v) may replace subtree rooted at u with subtree rooted at v by adjusting parent pointers; this simplifies deletion code by avoiding repetitive pointer updates. After deletion, verify with an inorder traversal to confirm the BST property is maintained.

Complexity and edge conditions
Finding the node and possibly its successor takes O(h) time where h is height. Thus deletion is O(h) with worst-case O(n) for skewed trees and O(log n) for balanced trees. Edge cases include deleting the root and deleting nodes with duplicate keys if duplicates are allowed—state the convention and handle accordingly.

Practical notes
Carefully update parent pointers if used; free or delete node memory to avoid leaks in manual memory management languages. When writing answers in exams, sketch the tree before and after each deletion step to show correctness clearly.

Why balance matters
The performance of search, insertion and deletion in a Binary Search Tree depends on the tree height h. If h is small—approximately logarithmic in the number of nodes n—operations take O(log n) time. If h is large—up to O(n) in a skewed tree—operations degrade to linear time. Balanced trees aim to maintain small heights so that operations remain efficient even in worst-case sequences of insertions and deletions.

Formal versus informal balance
Balance can be informal (subtrees roughly equal) or formal with strict numeric bounds. AVL trees enforce that the heights of left and right subtrees differ by at most 1 for every node. Red-Black trees enforce colour and path-length properties giving a guaranteed logarithmic height bound with less strict local constraints. These formal definitions permit proofs of worst-case time complexity.

Local rebalancing using rotations
When imbalance is detected after insertion or deletion, balancing algorithms perform local operations called rotations. Rotations rearrange a small number of pointers in a subtree while preserving the BST inorder sequence. Single rotations correct certain imbalances; sometimes double rotations are required. Rotations are constant-time operations that adjust subtree heights and restore balance locally.

Balancing strategies
Strategies include maintaining extra information per node (height, balance factor, or colour) to detect when to rebalance, and applying rotations or recolouring to restore invariants. Another approach is periodic rebuilding: when the tree becomes too unbalanced, extract its keys in sorted order and rebuild a balanced tree in O(n) time. Self-balancing trees do this incrementally during updates to maintain continuous guarantees.

Trade-offs and use-cases
Balanced trees require extra memory and code complexity for bookkeeping, but they provide predictably fast operations. For large databases, indexes and language runtimes where worst-case performance matters, balanced trees are preferred. For simpler or one-off tasks, an unbalanced BST may suffice, but awareness of skewed input patterns (e.g., sorted insertions) is essential.

Conceptual understanding over details
At this stage the unit focuses on the concept of balancing and why rotations help. Full implementations and proofs for AVL or Red-Black trees are taught elsewhere; here understand that maintaining height bounds keeps operations efficient and that rotations are the basic tool for local adjustments.

Heap definition
A binary heap is a special kind of binary tree that satisfies two properties: it is complete and it obeys the heap order property. Completeness means all levels except possibly the last are fully filled, and nodes in the last level are filled from left to right with no gaps. Heap order means that in a max-heap, each parent node's key is greater than or equal to its children; in a min-heap the parent key is less than or equal to its children. The combination of these properties makes heaps ideal for priority queues.

Array representation and index arithmetic
Because heaps are complete trees, they map naturally to arrays with no wasted interior gaps. Using 1-based indexing, for a node at index i the left child is at 2i, the right child at 2i+1, and the parent at floor(i/2). This arithmetic allows child and parent navigation using simple index calculations. Many languages use 0-based arrays; the analogous formulas adjust to left = 2i+1, right = 2i+2, parent = floor((i-1)/2).

Basic heap operations
Insert: add the new element at the end of the array (the next free position), then restore heap order by comparing with the parent and swapping repeatedly (sift-up) until the parent is larger (max-heap) or the root is reached. Extract-max (or extract-min): remove the root value, move the last element to the root position, decrease the heap size by one, and restore heap order by sifting the root down (sift-down) swapping with the larger child until the heap property holds.

Building a heap efficiently
Two approaches exist: repeated inserts (each O(log n) giving O(n log n) total) or bottom-up heap construction (also called heapify), which runs in O(n) time. Bottom-up heapify starts from the last internal node and calls sift-down for each internal node in reverse level order. This method works faster because most nodes are near the leaves and require only small sift-down work.

Complexity and memory
Heap operations insert and extract take O(log n) time because heap height is floor(log_2 n). Peek (reading the top priority) is O(1). The array uses O(n) contiguous memory and is compact because there are no pointer fields; this improves cache locality and often yields better performance in practice.

Applications
Heaps implement priority queues, are used in heapsort for in-place sorting, and appear in graph algorithms like Dijkstra’s algorithm (often using a priority queue). They are preferred when frequent access to the maximum or minimum element is required with dynamic inserts and deletes.

Priority queue abstraction
A priority queue stores elements with associated priorities and supports operations like insert (with a priority) and extract-max or extract-min. Binary heaps are a natural and efficient way to implement priority queues because they provide O(log n) insert and extract operations while using compact array storage. Accessing the top priority element is O(1) because it is always at the root.

Heapsort algorithm
Heapsort uses the heap to sort an array in-place. Steps: (1) build a max-heap from the input array (using bottom-up heapify in O(n) time); (2) repeatedly swap the heap root (maximum) with the last element, reduce heap size by one, and sift-down the new root to restore heap property. After n-1 such swaps, the array is sorted in ascending order. Heapsort is an efficient comparison-based sort with O(n log n) worst-case time and O(1) extra space (ignoring input array).

Why bottom-up build is important
Using bottom-up heap construction reduces total work because many nodes are near the leaves and require small sift-down operations. While repeated insertion costs O(n log n), bottom-up heapify runs in O(n). This difference matters when sorting large arrays because it directly influences total running time.

Stability and use-cases
Heapsort is not stable: equal elements may change relative order. Its advantages are predictable performance and low auxiliary memory usage. For in-memory sorting where stability is not required and predictable worst-case time is important, heapsort is a good choice. For stable sorts, merge sort or stable variants should be chosen.

Practical priority queue notes
In many programming frameworks a priority queue API is provided using a heap. When elements have complex priorities or a custom comparison is needed, define comparator functions carefully. For very large graphs or specialised algorithms, other heap variants like Fibonacci heaps offer better amortised bounds for decrease-key operations, but binary heaps remain simple and efficient in practice.

Exam-style reminders
Be ready to show array-to-heap mapping and steps of extract/insert operations. Explain why heap height is O(log n) and how that affects operation times. When asked, demonstrate heapsort steps on a small array to show understanding.

Pointer-based (linked) representation
In pointer-based representation every tree node is a structure or object with fields for data and two pointers (left and right) to children. This approach is natural for general binary trees because it represents any shape directly. It supports efficient local changes: inserting or deleting nodes only changes a few pointer fields. Parent pointers can be added if algorithms need to move upwards easily, though they use extra storage.

Advantages of pointer representation
Flexibility to represent sparse or irregular trees, straightforward rotations and relinking for balancing, and easy memory allocation for dynamic growth are its main advantages. For trees such as BSTs and expression trees where shape varies unpredictably, pointer-based nodes are typically used.

Disadvantages of pointer representation
Each node stores two pointer fields which increase memory overhead. Dynamically allocated nodes may be scattered in memory leading to poor cache performance. Manual memory management (allocation and freeing) increases coding complexity and potential for errors such as memory leaks or dangling pointers in languages without automatic garbage collection.

Array-based representation
For complete or near-complete trees an array representation is compact and very efficient. Using index arithmetic, children and parent positions are computed without explicit pointers: for 1-based indexing left(i)=2i and right(i)=2i+1, parent(i)=floor(i/2). This layout saves per-node pointer storage and improves locality because nodes are stored contiguously in memory, which is cache-friendly and often faster in practice.

Advantages and disadvantages of arrays
Arrays use contiguous memory and simple index math; they are ideal for heaps. However arrays waste space for sparse trees and require resizing strategies (e.g., doubling size) for dynamic growth. Representing arbitrary non-complete trees in arrays leads to many empty slots or complex index mapping, so arrays are usually reserved for heaps or complete trees.

Choosing representation
Choose pointer-based nodes for BSTs and general trees where shape changes unpredictably. Choose array-based storage for heaps and when you know the tree is complete or nearly complete. In interviews and exams justify the choice by citing memory, locality and operation complexity trade-offs.

Motivation for threading
Standard binary trees have NULL pointers where a child is absent. Inorder or other traversals require a stack or recursion to move between nodes. Threaded binary trees reuse these NULL pointers to store links (threads) to a node's inorder predecessor or successor, enabling traversal without extra memory for a stack or call frames. This technique trades pointer roles for traversal efficiency in certain contexts.

Types of threading
Single-threaded trees replace either left or right NULL pointers with threads (for predecessor or successor). Double-threaded trees use both left and right threads where appropriate. Each pointer needs a flag (or a special representation) to indicate whether it is a real child pointer or a thread; otherwise traversal would confuse threads with real child links.

Traversal without stack or recursion
In an inorder-threaded tree the right NULL of a node often points to its inorder successor. Starting from the leftmost node, repeatedly following successor threads yields the inorder sequence without a stack. For more general traversals threaded trees provide efficient navigation to next or previous nodes in traversal order, which can be beneficial in resource-constrained environments.

Insertions and deletions with threads
Maintaining threads complicates updates: when inserting or deleting a node, several threads in neighbouring nodes may need updating to preserve correct predecessor/successor links. Therefore threaded trees trade simpler traversal for more complex update logic. They are less common in modern high-level libraries but are instructive to understand alternative pointer use and optimisation techniques.

Practical relevance
Threaded trees were historically valuable in systems where recursion and stacks were expensive. They remain an interesting concept for exam questions and for demonstrating how data structures can be adapted to specific resource constraints. For most general programming tasks, recursive or iterative traversals with explicit stacks are preferred for their simplicity.

Study tips
Practice by sketching a small threaded tree and performing inorder traversal by following threads. Mark which pointers are threads and which are real children and trace updates for a single insertion to see how threads change.

What are expression trees
Expression trees represent arithmetic or logical expressions as binary trees where internal nodes are operators and leaves are operands (constants or variables). Because operators may be binary (e.g., +, -, *, /) the binary tree structure fits naturally: left and right children represent the left and right operands of the operator. Parentheses and operator precedence are encoded in the tree shape rather than relying on linear notation.

Constructing expression trees
A common method to construct an expression tree is to first convert infix notation into postfix (Reverse Polish) notation using a stack (the shunting-yard algorithm) that respects operator precedence and associativity. Then read the postfix expression: push operand nodes onto a stack; when an operator appears, pop the required operands, create a new operator node with those operands as children, and push back the new subtree. After processing all tokens the stack contains the expression tree root.

Traversals and notations
Traversals of the expression tree correspond to common notations: inorder traversal yields the infix expression (with parentheses needed to preserve original precedence), preorder yields prefix notation, and postorder yields postfix notation. Postfix is particularly useful because it can be evaluated by a simple stack machine without needing parentheses.

Evaluation of expression trees
Evaluate an expression tree using postorder traversal: evaluate left subtree to get a value, evaluate right subtree to get a value, then apply the operator at the current node. This recursive evaluation is straightforward and corresponds to how interpreters or calculators compute expression values. If operands are variables, evaluation uses a symbol table to provide values for leaves.

Applications and optimisations
Expression trees are used in compilers, interpreters and calculators. They support optimisations like constant folding (computing constant subexpressions at compile time) and algebraic simplification. They also help in code generation where tree structure guides the order of operations and resource allocation.

Practice exercises
Students should convert simple infix expressions to postfix, build expression trees from postfix, and then produce inorder and postorder outputs to confirm correctness. Tracing evaluation on numeric examples reinforces the recursive evaluation idea.

Measuring cost
When analysing tree algorithms the two primary measures are time and space complexity. Time complexity often depends on n (number of nodes) and h (height of the tree). Many tree algorithms are expressed in terms of h because operations like search, insert and delete follow a path whose length is bounded by height. Traversals visit all nodes and thus depend on n directly.

Traversal cost
Preorder, inorder, postorder and level-order traversals visit every node once and perform constant work per visited node (printing or processing). Therefore their time complexity is O(n). Space complexity for recursion-based traversals is O(h) due to the call stack; iterative level-order uses O(w) queue space where w is the maximum width of the tree (number of nodes at the largest level).

Search/insert/delete in BSTs
Search, insert and delete operations in a Binary Search Tree typically follow a single root-to-leaf path and so cost O(h) time. For a balanced BST h = O(log n) giving O(log n) search/insert/delete. For a skewed BST h = O(n) and operations degrade to O(n). When answering exam questions, explicitly state whether you assume a balanced tree or worst-case shape and provide both bounds if relevant.

Heap operation costs
Binary heap height is floor(log_2 n), so insert and extract operations cost O(log n) because they sift-up or sift-down along a path of length at most the heap height. Building a heap with bottom-up heapify is O(n) time while repeated insertion is O(n log n); this distinction is important for heapsort analysis.

Amortised and aggregate analysis
Some sequences of operations have amortised costs lower than worst-case per operation. For example, building a heap bottom-up spreads work unevenly across nodes so the aggregate time is O(n). Amortised analysis is useful when an expensive operation is rare and multiple cheap operations dominate average cost over a sequence.

Space and memory considerations
Pointer-based trees require O(n) memory for nodes plus pointer overhead; recursive routines require O(h) additional stack space. Array representations use O(n) contiguous space and often have better cache performance. When analysing algorithms, mention both time and space and justify bounds using heights, traversal counts or simple induction on subtree sizes.

Exam advice
State assumptions, define n and h clearly, and show reasoning: for example T(n) = T(left) + T(right) + O(1) leads to T(n)=O(n) for traversals. Provide both worst-case and balanced-tree bounds where appropriate and check units (edges vs nodes) when quoting heights.

Motivation for rotations
When a tree becomes unbalanced after insertions or deletions, rotations are the basic primitive to restore local balance while preserving the Binary Search Tree property. Rotations rearrange nodes and pointers in a small part of the tree, adjusting heights of subtrees and reducing imbalance. Understanding rotations conceptually prepares students for deeper study of balanced trees like AVL and Red-Black trees.

Right rotation explained
Consider a node y whose left child x exists. A right rotation at y makes x the new root of the subtree, with y becoming x's right child. Specifically, x's right subtree (if any) becomes y's left subtree. This operation is local: only pointers of x, y and the moved subtree change. The inorder sequence remains the same because nodes reorder without disturbing left-vs-right key relations.

Left rotation explained
Left rotation is the mirror of right rotation: for node x with right child y, a left rotation makes y the new root of that subtree and moves y's left subtree to x's right. Again the inorder ordering of keys is preserved and the local height distribution changes to reduce the heavier side.

Single and double rotations
Sometimes a single rotation suffices to correct imbalance; other times a double rotation is needed. For example, an insertion in the left-right case (left child with heavier right subtree) requires a left rotation on the left child followed by a right rotation on the parent (left-right double rotation). Double rotations combine two single rotations to handle more complex imbalance patterns.

Why rotations preserve BST property
Rotations reattach subtrees without changing the relative inorder order of nodes. Because the left subtree remains left of the pivot nodes and the right subtree remains right, all comparisons that define BST ordering continue to hold. This invariant is key to correctness and is why rotations can be used freely within balancing algorithms.

Practical notes
Rotations are constant-time pointer updates but require updating auxiliary fields (like height or balance factor) afterwards. While detailed rotation rules are covered in advanced units, being able to draw a before-and-after diagram and explain which pointers change is sufficient at this level. Practice by performing rotations on small trees to see how heights change.

Design considerations
Before coding, decide representation (pointer-based nodes or array), whether to store parent pointers, and what auxiliary fields (height, balance factor, colour) you need. For example, a simple BST needs only data and left/right pointers, while a self-balancing tree needs extra fields and rotation helpers. Document choices and ensure they match required operations.

Pseudocode clarity
Write clear, modular pseudocode using helper functions to avoid duplication. Typical helpers: findMin(node) to locate inorder successor, transplant(u,v) to replace one subtree with another, and rotateLeft/rotateRight for balancing. Use descriptive variable names and include base cases; for recursive functions always state the NULL base case explicitly.

Testing and debugging
Create a small set of test cases that cover edge conditions: empty tree, single-node tree, skewed trees, duplicate keys and deletion of root. Trace pointer changes step-by-step on paper for insert and delete to catch mistakes. Use inorder traversal after changes to verify the BST property by checking the sequence is sorted.

Memory management
In languages without automatic garbage collection, explicitly free node memory when deleting nodes to avoid leaks. Be careful to avoid dangling pointers: after freeing a node ensure no pointers in the program reference it. In garbage-collected languages rely on the runtime but still ensure correct pointer unlinking so objects become unreachable when intended.

Iterative versus recursive trade-offs
Recursive solutions are concise and easier to reason about; iterative solutions avoid call stack usage and can be preferable for very deep trees. For example, iterative inorder traversal uses an explicit stack while recursive traversal uses the call stack. Choose approach based on expected input size and environment constraints.

Exam implementation tips
When asked to write pseudocode in exams, include base cases and state complexity and space bounds. Use diagrams to show pointer changes for deletion and rotation questions. Small, well-commented pseudocode with helpers is clearer and scores better than long monolithic code.

Frequent question patterns
Examiners commonly ask students to: identify tree type from a diagram; perform traversals and give sequences; trace insertion and deletion steps in BSTs; convert between array and pointer representations; simulate heap operations like insert and extract; and analyse time complexity. Some questions may also require building expression trees or converting infix to postfix and back. Practising these patterns builds speed and accuracy.

Diagram and traversal strategy
For traversal problems simulate the exact order carefully. For preorder, write the node when first seen; for inorder, after finishing left subtree; for postorder, after finishing both subtrees. When given a tree diagram, mark visited nodes or keep a small scratch stack to avoid errors. Label depths and levels if asked, and show intermediate steps when performing insertions or deletions so marks can be given for partial progress.

BST operations in exams
When asked to insert or delete, show the tree after each operation. For deletion with two children, explicitly state whether you use the inorder predecessor or successor and show the replacement and subsequent node removal. Include brief commentary about pointer updates and maintain clarity on how parent/child links change to preserve the BST invariant.

Heap and array conversion questions
For heaps show array index calculations (left(i)=2i, right(i)=2i+1) and draw the tree to visualise swaps during sift-up or sift-down. For heapsort demonstrate the bottom-up build and then successive extract-max steps with arrays showing the state after each operation.

Complexity answers
Always specify assumptions: balanced vs arbitrary tree. Provide both average-case and worst-case bounds where appropriate. For example, say BST search is O(h) and then explain h = O(log n) for balanced trees and h = O(n) in the worst case. This clarity scores well in exams.

Practice plan
Solve past papers and time yourself. Focus on drawing clear diagrams, labelling steps, and practising pseudocode for deletion and heap operations. Use small examples to test corner cases like empty trees and single-node trees. Review mistakes and ensure you understand why errors occurred.

Condensed summary
Binary trees are hierarchical data structures with nodes having up to two children. Understand root, parent, child, leaf, subtree, depth and height. Know special tree types: full, perfect, complete, skewed and balanced, and what these imply about node counts and heights. Traversals — preorder, inorder, postorder and level-order — are fundamental tools: inorder of a BST gives sorted order. BSTs support search, insert and delete guided by key comparisons; heaps are complete trees supporting efficient priority operations and are stored in arrays.

Algorithmic reminders
Traversal time is O(n). BST search/insert/delete costs O(h) where h is height: balanced trees give O(log n), skewed trees give O(n). Heap insert and extract are O(log n); bottom-up heap build is O(n). Rotations are constant-time local operations used in balancing algorithms to keep height small. Space complexity includes node storage O(n) and recursion/stack space O(h).

Revision checklist — stepwise
1) Definitions: write down root, leaf, depth, height and subtree in your own words. 2) Types: sketch one example each of full, perfect, complete and skewed trees and annotate node counts and heights. 3) Traversals: practice preorder, inorder, postorder and level-order on 5 different small trees until sequences are quick to produce. 4) BST ops: practice search, insert and delete with clear intermediate diagrams and explain how inorder successor/predecessor is chosen for deletion. 5) Heaps: convert arrays to heaps, perform insert and extract showing array states and index calculations.

Common errors to watch for
Always state conventions: whether height is counted in edges or nodes, how duplicates are handled in BSTs, and whether array indexing is 0-based or 1-based for heaps. When drawing trees be precise about NULL children: missing links sometimes change whether a tree is complete or not. In deletion show both replacement and final removal steps to avoid partial-credit mistakes.

Practical practice plan
Schedule short daily drills: 10 minutes tracing traversals, 15 minutes writing pseudocode for one BST operation, and 10 minutes doing one heap exercise. Time yourself on past exam questions to build speed. Use hand-drawn diagrams and then write a one-line justification for each step to practise clear exam wording.

Final tips before exams
When solving a problem first state what you assume (e.g., duplicates go to right). For recursive solutions always write the base case. For complexity questions give both balanced and worst-case bounds. If asked to show steps, provide intermediate trees; partial credit is often awarded for correct intermediate work. Keep neat, labelled diagrams — clarity earns marks as much as correctness.