Binary search trees: ordering and search

From a binary tree to a search rule

The preceding lesson introduced a binary tree's root, left and right children, subtrees and traversal orders. A binary tree can hold arbitrary values; its shape alone does not tell you which branch contains a requested value. This lesson adds an ordering contract, then uses it to search a single downward path.

Prerequisites: the preceding binary-tree lesson, array-index links, struct, const array parameters, if, while, for and function return values. We retain the bounded record model value, left, right, CAP = 7 and END = -1. You will identify a valid binary search tree (BST), trace present and absent searches and explain what makes a branch safe to discard. This is a foundation lesson for GATE CS preparation, not full syllabus coverage.

The ordering rule applies to whole subtrees

Our BST stores distinct integer keys. At EVERY node:

• Every key anywhere in its left subtree is strictly smaller than that node's key.
• Every key anywhere in its right subtree is strictly larger than that node's key.
• Each subtree obeys the same rule recursively.

“Everywhere” includes grandchildren and deeper descendants. Checking only immediate children is insufficient. For example, a root 50 with left child 30 and a right child 55 under that 30 passes the two immediate comparisons 30 < 50 and 55 > 30. Yet 55 lies in the LEFT subtree of 50 and is greater than 50. The structure is a binary tree but is not a BST under our contract. This is a conceptual counterexample only; do not pass it to the search program below.

Ancestor restrictions accumulate. A node in the right subtree of 30 and the left subtree of 50 must be greater than 30 AND less than 50. One convenient paper check is to carry an allowed open interval down the path. No C arithmetic such as value - 1 or value + 1 is needed; those expressions could overflow at extreme int values.

Explicit duplicate policy

This lesson is search-only on unique keys. Duplicate keys are outside its valid-input contract. It implements no insertion, duplicate rejection routine, deletion or rebalancing. If you later add insertion to this model, an equal key should be reported as already present without creating a new node. Other BST designs can count duplicates or place equal keys on a specified side, but then their invariant and operations must be defined consistently. Do not silently mix those policies with this strict-order lesson. Searching for the same key twice does not add a duplicate or change the tree.

The bounded representation and caller promise

Node has three int fields in order: stored key value, left-child index left, and right-child index right. nodes[2].left reads a link; it does not read the left child's data. END means no node when used as root or a child link. A stored key of -1 is ordinary data. The integer returned by search is an INDEX, not the key.

For every call to bst_search, the caller must supply:

1. A live array of CAP initialized Node records, unchanged during the call. C adjusts const Node nodes[] to a pointer parameter; the function does not discover or allocate its capacity.
2. A root that is END or an index 0 through CAP - 1. Each reachable child link is likewise END or a valid index.
3. Reachable nodes forming a finite, acyclic rooted tree: no cycles and no node shared by two parent links. Every tree member is reachable from root. Unreachable array slots are spare storage and are not members; this model has no used count.
4. The strict global BST ordering above, with unique keys.

An empty tree uses root = END and may still have initialized records in its backing storage. Only reachability defines membership. The function trusts this contract; it is NOT a validator for arbitrary link fields. A bad index can cause an invalid C read, a cycle can prevent termination and bad ordering can hide a key. To process untrusted records, first add a separate structural and ordering validator; a mere index-range check is not enough. All runnable examples and tests in this lesson satisfy the promise.

One tree, two different orders

The program stores these records; root is index 2:

The root value is 50; its left subtree contains 30, 20 and 40; its right subtree contains 70, 60 and 80. Physical array order is 30, 70, 50, 20, 40, 60, 80. It is not sorted and does not need to be. Inorder traversal (left, node, right) produces 20, 30, 40, 50, 60, 70, 80. With unique keys, a valid BST's inorder values are strictly increasing. Preorder and postorder are not generally sorted.

Do not infer child indices using 2*i + 1 and 2*i + 2 here. This is an explicit-link representation with a root at index 2, not a level-order packed heap representation.

Search decisions and why they work

At current node x, first test equality. On equality, return x's index. If key < x.value, follow x.left: x itself is not the answer, and every key in its right subtree is too large. If key > x.value, follow x.right for the symmetric reason. Reaching END means the remaining candidate subtree is empty, so return END for absence. Do not read nodes[END].

The loop invariant is: if the requested key exists in the original tree and has not yet been found, it is in the subtree rooted at current. Each comparison preserves that statement while discarding the other branch. On a valid finite tree each step goes to a child, so the search eventually finds equality or reaches END. current moves; the stored root and all records remain unchanged.

Worked trace 1: present key 60

Three nodes are examined. The answer is 5, not 60. Read nodes[5].value only after establishing that the result is not END. The search never visits 30, 20, 40 or 80.

Worked trace 2: absent key 65

This does not mean 65 is numerically invalid; it simply is not stored. Looking in the left subtree of 50 after this failure would be pointless under the BST invariant.

Worked trace 3: empty and one-node boundaries

With root = END, any search executes zero loop iterations and returns END. With root = 0 and node 0 = { -1, END, END }, search(-1) examines one node and returns index 0. Search(0) goes right to END and returns END. Search(-2) goes left to END and returns END. In each case END is tested before indexing; a key equal to -1 is never confused with absence because a found result is its nonnegative index.

Complete C11 program

This complete program uses only initialized fixed-size storage and no dynamic allocation. The contract above is a required precondition, not a claim of runtime validation.

#include <stdio.h>

enum { CAP = 7, END = -1 };

typedef struct {
    int value;
    int left;
    int right;
} Node;

/* Caller supplies CAP initialized records and a valid unique-key BST.
   root is END or a valid index. Every reachable link is END or an
   index in [0, CAP). Reachable nodes form an acyclic tree (no sharing).
   At every node, all left-subtree keys are smaller and all right-
   subtree keys are larger. Unreachable slots are not tree members. */
int bst_search(const Node nodes[], int root, int key) {
    int current = root;
    while (current != END) {
        if (key == nodes[current].value) {
            return current;
        }
        if (key < nodes[current].value) {
            current = nodes[current].left;
        } else {
            current = nodes[current].right;
        }
    }
    return END;
}

int main(void) {
    const Node nodes[CAP] = {
        {30, 3, 4},
        {70, 5, 6},
        {50, 0, 1},
        {20, END, END},
        {40, END, END},
        {60, END, END},
        {80, END, END}
    };
    const int root = 2;
    const int keys[3] = {60, 65, 50};
    for (int i = 0; i < 3; i = i + 1) {
        int index = bst_search(nodes, root, keys[i]);
        if (index == END) {
            printf("%d: absent\n", keys[i]);
        } else {
            printf("%d: index %d, value %d\n",
                   keys[i], index, nodes[index].value);
        }
    }
    return 0;
}

Exact output:

60: index 5, value 60
65: absent
50: index 2, value 50

Equality is checked before the less-than branch, so the final else means strictly greater. The code compares integers directly rather than subtracting them, allowing keys as small as INT_MIN and as large as INT_MAX without comparison overflow. const prevents writes through this parameter; it does not make malformed input valid.

Cost follows height, not the word “binary”

Use the preceding lesson's height convention: a nonempty tree's height h counts edges on its longest root-to-leaf path; a singleton has height 0. Search examines at most h + 1 nodes, and an empty tree examines none. A success at the root examines one node. Each node visit performs only a constant amount of work, so worst-case search time on a nonempty tree is O(h + 1); the iterative search uses O(1) extra space. The CAP-record input array is existing storage, not newly allocated working memory.

Here O(...) describes an upper bound on how resource use grows, ignoring fixed constant factors for sufficiently large inputs. O(1) extra space means a fixed amount independent of n. O(log n) grows logarithmically: doubling n adds only a bounded amount to that growth scale. O(n), called linear growth, allows work proportional to the number of nodes. A bound describes a limit, not a claim that every search uses the maximum.

In a balanced family of BSTs the height grows logarithmically with node count n, giving logarithmic worst-case search. The BST ordering rule alone does not guarantee balance. A chain 10 ->right 20 ->right 30 ->right 40 is a valid BST of height 3. Searching for 40 examines four nodes. In a longer chain it can examine all n nodes, so worst-case BST search can be linear. These growth statements concern the same algorithm at larger capacities; this demonstration itself is bounded by seven records. Completeness, fullness and perfection are shape properties, separate from BST ordering.

A bounded analogy

Imagine a directory of seven numbered rooms. Each room displays a unique number to look up and two signposts. The left signpost leads to a section containing only smaller numbers; the right signpost leads to a section containing only larger numbers. All later rooms must also obey the restrictions from earlier signposts. The room label is an array index; the displayed number is its key. A “no room” sign ends the search without entering another room.

This analogy explains why one section can be skipped. It assumes correct signs, no loops and the stated global ordering. It does not guarantee equal-sized sections, logarithmic travel time or safe behavior with corrupt signs. Real BSTs need not use numbered array slots.

Key box

• Binary-tree shape alone does not provide search ordering.
• Compare every descendant against all relevant ancestor bounds, not just its parent.
• Unique keys use strict left-smaller and right-larger subtree rules.
• Search follows one branch per unsuccessful node comparison; it is not a full traversal.
• Return an index on success and END on absence; -1 may still be a stored key.
• Empty is root = END. Search changes neither root nor records.
• O(h + 1) node-search work does not imply O(log n) without a height guarantee.
• The caller supplies valid storage, links, structure and ordering; this search does not validate them.

Two extra exercises with checks

1. In the seven-node example, trace search(40) and search(10). Check: 40 visits indices 2, 0, 4 and returns 4. For 10, visit 2, 0, 3, then the left link END; return END. Both examine three nodes, although only one succeeds.
2. Replace only value 40 at index 4 by 55 on paper. Which rule fails, and why must the modified records not be passed as a valid BST? Check: 55 is greater than its parent 30 but lies in root 50's left subtree, violating the ancestor upper bound. Searching for 55 would take root's right branch and miss it. This is a logical illustration, not a valid-input program test.

Six original practice questions

Choose exactly one option. These are original foundation exercises, not previous-year questions or a full mock examination.

1

A root 50 has left child 30, and that 30 has right child 55; there are no other nodes. Which statement is correct?

A. It is a valid BST because each child compares correctly with its parent. B. It is not a BST because 55 violates the bound from ancestor 50. C. It is not a binary tree because 30 has a right child. D. It becomes a valid BST merely by storing the records at sorted array indices.

2

For the seven-node program tree, which indices does search(60) examine, and what does it return?

A. 2, 0, 4; returns 4 B. 50, 70, 60; returns 60 C. 2, 1, 5; returns 5 D. 2, 1, 6; returns END

3

A valid singleton has root = 0 and nodes[0] = {-1, END, END}. What does bst_search(nodes, root, -1) return?

A. 0 B. END, because -1 cannot be a key C. 1, because a match is true D. The value of nodes[-1]

4

Under this lesson’s policy, which input is permitted for bst_search?

A. A cyclic structure, provided every index is within bounds B. Any binary tree, regardless of key order C. A tree with duplicate keys placed on either side arbitrarily D. An acyclic, non-sharing tree with valid links and strict unique-key subtree ordering

5

A valid BST is the chain 10 ->right 20 ->right 30 ->right 40. How many nodes are examined when searching for 40?

A. One, because 40 is the largest key B. Two, because every BST search halves the node count C. Four, because ordering does not guarantee a balanced shape D. Three, because height counts edges

6

For the seven-node program tree, what happens when searching for 65?

A. The search returns index 5 because 60 is the closest visited value. B. It follows indices 2, 1, 5, then END, and returns END. C. It reads nodes[-1] to confirm absence. D. It must traverse the entire left subtree after the right-side search fails.

Worked answers

1. B

A is incorrect: immediate parent comparisons miss restrictions inherited from ancestors.

B is correct: every node in the left subtree of 50 must be smaller than 50, including 55.

C is incorrect: a binary-tree node may have a right child; this shape is allowed.

D is incorrect: BST order concerns values along subtree relationships, not physical array order.

2. C

A is incorrect: 60 is greater than root key 50, so the first branch is right, not left.

B is incorrect: those numbers are keys, not indices; success returns index 5.

C is correct: compare with 50, then 70, then 60 at indices 2, 1 and 5.

D is incorrect: at key 70 the smaller target 60 sends the search left to index 5, not right to 6.

3. A

A is correct: equality at node index 0 returns 0; the key and return index have different roles.

B is incorrect: END is a sentinel for links and the returned index, not a ban on key -1.

C is incorrect: this API returns an index, not a Boolean success flag.

D is incorrect: equality returns index 0 without reading an END index.

4. D

A is incorrect: bounded indices do not remove cycles; acyclicity is a required caller promise.

B is incorrect: search discards branches based on ordering, which a general binary tree need not have.

C is incorrect: duplicate keys are outside this lesson’s contract; no arbitrary duplicate policy is allowed.

D is correct: these are the structural and ordering requirements, together with the promised initialized CAP-record storage.

5. C

A is incorrect: without an extra maximum pointer, this search starts at root 10 and follows links.

B is incorrect: a chosen subtree may contain nearly all remaining nodes; balance is not automatic.

C is correct: the visits are 10, 20, 30, 40; height is 3 but visited nodes are h + 1 = 4.

D is incorrect: three edges connect four visited nodes; edge count and node visits differ.

6. B

A is incorrect: this is exact-key search, not a nearest-value query; 60 is not 65.

B is correct: comparisons lead right from 50, left from 70, then right from 60 to an empty subtree.

C is incorrect: the while condition stops before indexing END.

D is incorrect: every key in root 50’s left subtree is less than 50 and cannot equal 65.

Scope and next step

You can now distinguish tree shape from search ordering and trace exact-key lookup safely under an explicit contract. Next compare BST ordering with heap ordering. Insertion, deletion, balancing and formal correctness proofs need further lessons. This offline lesson changes no course year, price or access setting. Hindi supports learning; it does not imply an official Hindi GATE paper.