Programming in C and Data Structures

Binary search tree operations

A binary search tree (BST) is a binary tree in which, for every node, every key in its left subtree is smaller than the node's key and every key in its right subtree is larger. Because of this rule, an inorder traversal of a BST with distinct keys always visits the keys in ascending order, whatever the insertion history was.

The shape of a BST is not fixed by its key set. The same keys inserted in different orders can produce different trees, so the root, the preorder sequence and the postorder sequence may all differ. Only the inorder sequence is determined by the set alone, so a statement about the root or about preorder cannot be concluded from the keys by themselves.

Search, insertion and deletion follow a single path from the root and compare keys at each node, so their cost is proportional to the depth of the node involved. In a balanced tree the height is about \log_2 n, which gives O(\log n) time. If keys arrive in sorted order, however, the tree degenerates into a chain with n-1 edges from root to the deepest node, and the worst case becomes O(n).

Selecting some element that is not the maximum needs no search, because the root or its left child is directly accessible; such a selection takes a fixed number of pointer accesses, that is \Theta(1).

When a complete binary tree is stored in an array with indices starting at 0, the children of index i are at 2i+1 and 2i+2, and the parent is at \lfloor (i-1)/2 \rfloor. The k-th largest key of a BST is found by walking the right spine from the root and taking inorder predecessors, and in the array form each step is an index computation.

The number of edges on the path from a node up to the root equals its depth, so it is found by counting parent steps. For example, if a key is inserted as the left child of a node that is the right child of the root, its depth is 2.

A node can enter the tree only after its ancestors, so every valid insertion sequence lists each parent before its children. In a complete BST on a fixed key set, the third inserted key must therefore lie within depth two of the root.

The inorder successor of a node with no right child is its nearest ancestor whose left subtree contains that node. A leaf has no right child, so a new key lying between a leaf and its successor can be attached as the leaf's right child, and each such attachment raises the height by at most one. Keys placed in disjoint gaps between consecutive inorder keys are necessarily distinct.

Recursive function tracing

Recursion is a function calling itself on a smaller argument. Tracing it means reconstructing the value returned by each call. A correct recursive function has a base case, tested without any recursive call, and a recursive step that moves the arguments toward that base case. When the base case is checked first, its return overrides every later branch, so the order of the if-statements matters.

A systematic way to trace is to write each branch as an equation, for instance F(x,y)=F(x,y-q)+F(x-q,y), compute the base values, and substitute upward. When a function adds two recursive calls, its value is the sum over all paths of the recursion tree, so counting how often each base case is reached gives the answer quickly.

Subtracting the smaller argument from the larger until both are equal is Euclid's subtraction method, and the function computes the greatest common divisor of its positive arguments.

Every call creates a new activation with its own copy of local variables. Code that runs before a recursive call is performed on the way down, while code that runs after the recursive call returns is performed during unwinding, so the output of the second kind appears in reverse order of the calls.

The activation tree records every call as a node whose children are the calls made from its body, in the order they are written. A call to a function from inside a recursive chain creates a nested node, so the depth of the tree equals the depth of the recursion.

A function that halves its argument with integer division descends about \log_2 n levels, since integer division truncates. For example, g(n)=g(n/2)+1 with g(1)=0 returns \lfloor \log_2 n \rfloor.

Passing S+1 together with size minus one treats the array as starting at its next element, so each call examines a window of adjacent pairs and the recursion walks the array from left to right.

When a function's behaviour depends only on its argument modulo some number, compute small cases first to see which values can be returned, and then extend the pattern by the period.

C operator precedence and evaluation

In C, the order in which operators are applied is set by precedence and associativity. Multiplicative operators bind more tightly than additive ones, which bind more tightly than shifts, relational operators, equality operators, the bitwise AND, XOR and OR, the logical operators, the conditional operator and assignment, in that order. Associativity decides grouping among operators of equal precedence: arithmetic operators are left-associative and assignment is right-associative. Parentheses override both rules. A common trap is that bitwise AND has lower precedence than equality, so an expression such as x \text{ \& } m == 0 is grouped as x \text{ \& } (m == 0).

Integer division truncates toward zero, so the value of 9/4*2 is 4, because 9/4 is first 2. A division of small integers can therefore produce zero, which changes what later updates compute.

The logical operators are evaluated left to right with short-circuiting. The right operand of && is evaluated only when the left operand is true, and the right operand of || only when the left is false, so an increment placed in a skipped operand never occurs. The postfix ++ yields the old value and then increments the variable.

Character operands are promoted to int before arithmetic or bitwise operations, and the result is converted back to char on assignment. The printed output therefore depends on the character codes of the operands and on any offsets added to them.

A static local variable keeps its value between calls. In C the order in which operands of an expression are evaluated is unspecified, so an expression that calls functions with side effects must not depend on that order. Assignments completed in an earlier statement are safe to use later.

When a problem supplies its own precedence and associativity table, apply that table exactly rather than the usual C rules. For a right-associative division, a/b/c is grouped as a/(b/c).

The same discipline of grouping applies to rational expressions in mathematics. When a quotient takes the form 0/0 at a point, a factor vanishing in both numerator and denominator must be cancelled before substitution.

Stack and queue operations

A stack is a last-in, first-out structure: push and pop act on the top, so the most recently pushed element leaves first. A queue is first-in, first-out: enqueue adds at the rear and dequeue removes from the front. Questions on sequences of operations are solved by tracking the contents after each step, writing the top of the stack on the right and the front of the queue on the left. The value returned by pop or dequeue is fixed at the moment the element is removed.

Operations on two structures can be combined. Removing an element from a queue and pushing it onto a stack moves it from one structure to the other, which changes the order in which it will be read later. Each such transfer must be simulated in sequence.

A queue can be rotated using only its own operations: dequeuing the front element and enqueuing it again moves that element to the rear. Rotations of one queue, combined with transfers to a second queue, can reverse or rearrange the order of elements, and only the enqueue operations on the target queue count toward the measure asked for.

With two stacks of limited capacity, the elements of one stack can be reordered only by moving them to the other. An element can be output only when every element above it has been moved away, and the capacity of the auxiliary stack limits how many elements can be set aside at once. A candidate output is achievable if a sequence of legal moves produces it, which is checked by simulating the moves.

Augmenting a stack with a constant-time MIN requires that a pop restore the previous minimum. The standard method stores with each record the minimum of that record and all records beneath it. This value is computed in constant time on push and needs no update on pop. A single global minimum pointer fails, because removing the minimum record requires scanning the stack. A sorted auxiliary array or a min-heap keeps MIN fast but makes push and pop more expensive.

When a stack is emptied first and then a queue, the output begins with the stack's elements in reverse order of their pushes, followed by the queue's elements in order of arrival. Checking whether a given output is possible therefore amounts to splitting it into a decreasing part and an increasing part and checking that each element can be assigned consistently.

Struct pointers and linked list manipulation in C

A struct groups named fields, and a pointer to a struct accesses a field with the arrow operator, so p \to f is the same as (*p).f. Dereferencing requires the pointer to hold a valid address, so the arrow must never be applied to NULL or to an uninitialized pointer.

Memory returned by malloc is not initialized. A newly allocated node therefore has indeterminate contents, including its next field, until the program assigns it. Reading an indeterminate value, or dereferencing a pointer obtained from one, is undefined behaviour and may crash the program. In C99 and later, reaching the closing brace of main returns 0 implicitly, so a missing return is not a compile error.

Repeated subexpressions, such as a field read through the same pointer or a sum of constants, can be reduced by common subexpression elimination, which computes each value once and reuses it. Expressions whose operands do not change inside a loop can be hoisted out of it. Counting operations in optimized code requires noting which expressions depend on the loop variable and which remain constant.

Deleting a node from a singly linked list requires changing the next pointer of its predecessor, which is not stored in the node. Given only the node and the head, the predecessor must be found by traversing from the head, so the worst case is O(n). A doubly linked list stores a prev pointer in each node, so the links can be redirected in constant time.

Post-order processing visits both children before the node itself. A recursive function that computes a subtree's total and prints it after the two recursive calls therefore prints each subtree's sum, with the values of children appearing before those of their parent.

When nodes are removed while a list is scanned, the scanning pointer must stay at its position after a deletion so that the node now following is examined. It advances only when a node is kept. A loop that starts from the second node never examines the head node, so the head is unaffected by its test.

Recursion on a list passes the pointer to the next node as the argument of the smaller problem. The base case must test the next field, rather than the head itself, so that a one-node list returns without a null dereference and without an argument that never shrinks. The function is intended for non-empty lists.

Pointer arithmetic and indirect assignment

A pointer stores an address, and the expression *p denotes the object stored at that address. An assignment through *p therefore changes the pointed-to object, not the pointer itself, so the same object can be modified through a different name or pointer. Pointer arithmetic is scaled by the size of the element type, so p+1 addresses the next element of an array, and \&z[0]+1 is the same address as \&z[1]. Subtracting two pointers of the same type gives the number of elements between them, not the number of bytes, whereas subtracting the dereferenced values is ordinary arithmetic on the stored numbers. When a pointer is passed to a function, the callee can write through it, so an assignment such as *p = x inside the function changes the caller's variable. A loop that advances a source pointer and a destination pointer together copies one character at a time and stops when the source reaches the null terminator, which is not copied, so any original characters beyond the copied length remain visible. Operator precedence matters here: *p{+}{+} increments the pointer after reading the value it pointed to, while (*p){+}{+} increments the value itself. Reassigning a pointer redirects all later dereferences to a different object, so the value read through the pointer after the redirection comes from the new target.

Binary heap operations

A binary heap is a complete binary tree stored in an array. With 1-based indexing, the children of index i are at 2i and 2i+1, and the parent of i is at \lfloor i/2 \rfloor. A max-heap requires every parent to be at least as large as each of its children, while a min-heap requires every parent to be at most as large as each child. To check whether an array is a max-heap, compare each index i with its children that lie within the array, since the parent-child relation alone determines the heap property. Insertion appends the new key at the last position and moves it upward along one path to the root, so its worst-case cost is proportional to the height \lfloor \log_2 n \rfloor. Extracting the maximum removes the root, moves the last element to the root and sifts it downward, which also costs O(\log n) in the worst case, whereas only reading the root is O(1). Heapify builds a heap from an arbitrary array by sifting down each internal node, starting from index \lfloor n/2 \rfloor and working back to the root. In a binary heap with n nodes the leaves are exactly the indices from \lfloor n/2 \rfloor + 1 to n, so the number of leaves is n - \lfloor n/2 \rfloor. In a min-heap every parent is smaller than its descendants, so the maximum element cannot have children and must sit at a leaf. The height of a complete binary tree with n nodes, measured in edges, is \lfloor \log_2 n \rfloor. For odd n = 2k+1, the parent of index n is k, so the indices k and k-1 are internal nodes, not leaves. Students should note that a heap guarantees only parent-child order, not a sorted array, so the first elements after heap construction need not be in ascending or descending order.