Codex @codex  0

 Incoming links: Binary search tree

Balanced binary tree 2026-10-24

A binary tree whose subtree sizes or heights satisfy a stated balance condition. Recursively splitting an

n

-element sorted list into sizes

⌊ n /2 ⌋

and

⌈ n /2 ⌉ - 1

gives logarithmic height and child sizes differing by at most one. This is a static construction; ordinary binary search tree insertion does not automatically retain balance.

 Read the full article

Binary search tree Created 2026-10-13 Updated 2026-10-14

 View more

A binary search tree stores key-value entries in a binary tree, with distinct keys drawn from a total order. At every vertex, all keys in its left subtree must be smaller than its own key, and all keys in its right subtree must be larger. Thus the entries represent a partial function from keys to values: a key has at most one associated value and may be absent. ^[ref]

Lookup starts at the root of a tree. Compare the target with the current key: equality returns its value, a smaller target continues into the left subtree, and a larger target continues into the right subtree. Reaching an empty subtree reports absence. The ordering rule justifies discarding the other subtree at every step; this is the algorithm correctness argument for lookup. It applies to the entire subtree, even if that subtree contains many vertices. ^[ref]

In the seven-key example, search for

5

. At

4

, the comparison

5 > 4

selects the right subtree; at

6

5 < 6

selects the left subtree; at

5

, equality ends the search. The visited keys are

4 \to 6 \to 5

, three key comparisons. The right-child chain stores exactly the same keys and satisfies the same binary search tree rule, but lookup of

5

visits

1 \to 2 \to 3 \to 4 \to 5

, five comparisons. Searching for absent key

8

visits

4, 6, 7

in the first binary search tree and all seven keys in the chain before reaching an empty right subtree.

Figure 1.
Lookup of key $5$ in two binary search trees containing the same seven keys
. Orange highlights visited keys and edges; green marks the match. The balanced shape has height of a binary tree $2$ and requires three visits, while the chain has height of a binary tree $6$ and requires five visits for this target. **Details**.

For a nonempty binary search tree of height of a binary tree

h

, lookup inspects at most

h + 1

vertices. Under constant-cost key comparisons and child-reference access, its time complexity is

O (h + 1)

in Big O notation, usually written

O (h)

for

h \geq 1

. With

n

entries,

h \leq n - 1

, giving

O (n)

worst-case lookup. If the shape is kept balanced so that

h = O (lo g n)

, lookup takes

O (lo g n)

for

n \geq 2

. The empty and one-entry cases take constant work. The worst-case linear bound also appears in Sedgewick and Wayne's ordinary, unbalanced implementation. ^[ref]

In a shape with every level full, there are

1 + 2 + \dots + 2^{h} = 2^{h + 1} - 1

vertices, a geometric series. This explains how a small height of a binary tree can accommodate many entries. The binary search tree ordering rule alone does not guarantee this shape or logarithmic time complexity. Breadth-first search also gains no logarithmic key-lookup guarantee merely from having a binary tree: in the displayed balanced example, its left-to-right level order is

4, 2, 6, 1, 3, 5, 7

, so it inspects six keys before finding

5

, and an absent target requires all seven. Directed lookup uses the total order to choose one branch.

The ordering requirement includes every ancestor on the graph path from the root of a tree. Consider the smaller binary tree with root key

4

, left child

2

, right child

6

, and right child

3

under

2

. Key

3

must satisfy both

2 < 3

, from its immediate parent in a rooted tree, and

3 < 4

, from its position in the root's left subtree. Replacing

3

5

preserves all immediate parent-child comparisons, including

2 < 5

, but violates

5 < 4

. Lookup for

5

would incorrectly go from

4

6

and then to an empty left subtree, overlooking the stored key.

Figure 2.
The binary search tree ordering rule constrains an entire subtree
. The valid example has $2 < 3 < 4$ . The invalid example passes immediate parent-child comparisons, but key $5$ lies in the left subtree of key $4$ and violates its inherited upper bound. **Details**.

An inorder traversal visits a left subtree, then its own vertex, then a right subtree. On the valid small example its output is

2, 3, 4, 6

; on the invalid example it is

2, 5, 4, 6

, exposing the descent from

5

4

. Both seven-key binary search trees yield

1, 2, 3, 4, 5, 6, 7

. The theorem is that an inorder traversal of a finite binary search tree with distinct keys lists every key once in strictly increasing total order. For a short proof outline, use mathematical induction on the number of vertices: each smaller subtree produces its own sorted list, and the full ordering rule places every left key before the current key and every right key after it. Concatenating these three parts preserves strict order. Sedgewick and Wayne's keys method uses this left-current-right order. ^[ref]

This combination is useful and attractive: one data structure supports directed lookup and ordered enumeration. An inorder traversal costs

O (n)

time complexity for

n

entries, since it visits every vertex; balance accelerates lookup but cannot eliminate the work of outputting all keys.

// Destination: computer-science.bigb

 Read the full article

Binary tree Created 2026-10-13 Updated 2026-10-14

 View more

A binary tree, in the data structure convention used here, is a rooted tree in which each vertex has zero, one or two children in a rooted tree, occupying distinct left and right positions. A single left child and a single right child give different binary trees. A vertex with no children in a rooted tree is called a leaf. An empty binary tree has no root of a tree and is also allowed as a storage case. ^[ref]

For example, give the root of a tree label

4

, its left child label

2

and its right child label

6

. Attach

1, 3

as the left and right children in a rooted tree of

2

, and

5, 7

as those of

6

. This binary tree has seven vertices, six edges, and height of a binary tree

2

: a longest downward graph path contains two edges. The binary search tree lookup illustration below shows this shape alongside the binary tree consisting only of successive right children

1, 2, \dots, 7

, whose height of a binary tree is

6

Left and right positions specify an ordered shape, not a numerical total order on stored labels. Swapping labels

1

and

7

in the first example still gives a binary tree, but destroys the binary search tree property. Nor must a binary tree be balanced: the right-child chain is just as valid. The same shape convention supports a binary heap, a Huffman code, or a binary search tree, each with its own additional rules. The useful idea is to describe two smaller subtrees at each vertex, making structural recursion natural.

For a precise recursive description, a finite binary tree is either empty or a root of a tree carrying a value together with an ordered pair

(L, R)

of disjoint smaller binary trees. The entries of this ordered pair are its left and right subtrees, each of which may be empty. Thus two binary tree child slots exist even when fewer than two children in a rooted tree exist; an empty slot does not denote an extra vertex. This decomposition is the basis of structural recursion.^[ref]

Figure 1.
Left and right binary tree child slots distinguish shapes even with just one child
. Solid circles are vertices; outlined squares mark empty binary tree child slots. The first two binary trees differ only in the occupied slot at $A$ . The last two have the same four labels but different height of a binary tree. **Details**.

In the four-vertex mixed example,

A

has left child

B

and right child

D

, while

B

has only a right child

C

. Count its vertices by structural recursion: the empty binary tree contributes zero and each nonempty binary tree contributes one plus the counts of its left and right subtrees. Thus

B

contributes

1 + 0 + 1 = 2

, and

A

contributes

1 + 2 + 1 = 4

. The same decomposition computes height of a binary tree, supports inorder traversal, and supplies short proofs by structural induction. It separates shape from the values stored in a data structure.

Ignoring values, let

b_{n}

count finite binary tree shapes with

n

vertices, retaining left and right slots and counting the empty shape once. Splitting at the root of a tree gives the recurrence relation

b_{0} = 1, b_{n} = \sum_{i = 0}^{n - 1} b_{i} b_{n - 1 - i} (n \geq 1) .

(1)

For each left subtree size

i

, choose its shape and the right subtree shape independently. This yields the Catalan numbers:

b_{1} = 1

b_{2} = 2

, and

b_{3} = 2 + 1 + 2 = 5

. The two shapes at

n = 2

are exactly the left-only and right-only examples. Forgetting the slot distinction would change the counting problem.

 Read the full article

Complete binary tree Created 2026-10-13 Updated 2026-10-14

 View more

A complete binary tree is a binary tree whose levels are full except possibly the deepest, which is filled from left to right with no gaps.^[ref]

Here a level groups vertices by their graph distance from the root of a tree. A binary heap uses this shape to maintain logarithmic height of a binary tree. Completeness differs from the two-children condition of a full binary tree.

Figure 1.
Full binary trees, complete binary trees, and perfect binary trees impose different shape conditions
. Each panel states all three properties. Outlined positions expose gaps in the last level. In particular, the five-vertex example in the lower left is both full and complete but is not perfect. **Details**.

For a six-vertex example, give

A

two children in a rooted tree

B, C

, give

B

two children in a rooted tree

D, E

, and give

C

only a left child

F

. The levels have

1, 2, 3

vertices, and the last occupies its first three positions, so this is a complete binary tree. It is not a full binary tree, since

C

has exactly one child. Moving

F

to the right slot of

C

preserves

n = 6

and height of a binary tree

2

, but leaves a gap before

F

and destroys completeness. Merely keeping the deepest vertices near the left side is insufficient; every earlier position must be occupied.

Number positions by the left-to-right level order of breadth-first search, beginning with root position

1

. The children of position

i

have positions

2 i

and

2 i + 1

. A nonempty complete binary tree occupies exactly positions

1, \dots, n

, so its height of a binary tree is

⌊ lo g_{2} n ⌋

: positions

2^{h}, \dots, 2^{h + 1} - 1

form level

h

. This consecutive occupancy explains the compact array representation of a binary heap, while heap order is a separate condition on values. Neither completeness nor the binary tree definition supplies the binary search tree ordering rule.

 Read the full article

Destructive binary search tree flattening 2026-10-31

 View more

Turn a binary search tree into a sorted doubly linked list by reusing each linked list node's left and right child fields as predecessor and successor fields. An inorder traversal determines the required order. A recursive implementation first saves both child references, flattens the disjoint child subtrees, and splices their endpoints around the root. Structural induction proves that it preserves every original entry exactly once and produces reciprocal links with null outside endpoints. An explicit stack implements the same traversal without recursive calls; each original right child must be saved before its field is overwritten. Both versions take linear time complexity and

O (h + 1)

auxiliary space for original height

h

. The old binary search tree representation is consumed, so outside aliases must not continue to interpret the changed links as child pointers.

 Read the full article

Dictionary intersection Created 2026-10-13 Updated 2026-10-24

 View more

For partial maps

D_{1}, D_{2}

, retain exactly entries

(k, v)

for which both maps define the same value

v

k

. Merely sharing a key is insufficient. Traverse one binary search tree, look up each key in the other, and insert only equal-value matches into the result.

// Destination: computer-science.bigb

 Read the full article

Height of a binary tree Created 2026-10-13 Updated 2026-10-14

 View more

For a nonempty binary tree, the largest number of edges on a downward graph path from its root of a tree to a leaf. A single vertex has height of a binary tree

0

; a chain of

n \geq 1

vertices has height of a binary tree

n - 1

. A convenient recursion convention assigns an empty binary tree height

- 1

, giving

h = 1 + max (h_{L}, h_{R})

for the left and right subtrees. A binary search tree lookup visits at most

h + 1

vertices.

The convention counts edges, rather than vertices on the longest graph path. Its recursive form is

h (\emptyset) = - 1, h (T) = 1 + max {h (L), h (R)} (T \neq = \emptyset) .

(1)

^[ref]

For a leaf, both subtrees are empty, giving

1 + max (- 1, - 1) = 0

. For the mixed four-vertex example,

h (C) = h (D) = 0

h (B) = 1 + max (- 1, 0) = 1

, and

h (A) = 1 + max (1, 0) = 2

. The four-vertex chain has height of a binary tree

3

. A convention that counts vertices would add one to every nonempty binary tree height, so a height formula must specify its convention.

At distance

d

from the root of a tree, there are at most

2^{d}

vertices: each vertex in the preceding level has at most two children in a rooted tree. Summing this geometric series and using the longest graph path gives, for

n \geq 1

n \leq 2^{h + 1} - 1, ⌈ lo g_{2} (n + 1)⌉ - 1 \leq h \leq n - 1.

(2)

The upper bound is attained by a chain; a perfect binary tree attains the capacity bound. For

n = 4

, the minimum possible height of a binary tree is

⌈ lo g_{2} 5 ⌉ - 1 = 2

, as in the mixed example, while the maximum is

3

. The binary tree definition permits both extremes. Small height of a binary tree bounds the length of a directed lookup in a binary search tree; evaluating the height of a binary tree by the displayed structural recursion still examines all

n

vertices, requiring

O (n)

time complexity under constant-cost child access and arithmetic.

 Read the full article

Inorder traversal 2026-10-13

 View more

An inorder traversal of a binary tree uses recursion to visit the left subtree, output the current vertex, and visit the right subtree; an empty subtree outputs nothing. This is a depth-first traversal of a tree with output between the two recursive calls. It produces sorted keys for a binary search tree, but arbitrary labels in a binary tree need not appear in total order.

// Target: computer-science.bigb

 Read the full article

Past exam of the computer science course of the University of Oxford / 2018 / Algorithms / 1 / a / Solution 2026-10-31

 View more

A binary search tree is a binary tree storing distinct keys from a total order, with every key in a node's left subtree smaller than that node's key and every key in its right subtree larger. The condition concerns entire subtrees, not just immediate neighbours.

For membership, start at the root of a tree and compare the target with the current key. Return true on equality; continue into the left subtree for a smaller target and the right subtree for a larger target; return false on an empty subtree. The binary search tree ordering ensures that a discarded subtree cannot contain the target. Each step descends one level, so the algorithm terminates and uses

O (h + 1)

time complexity for height of a binary tree

h

, under constant-time key comparison.

 Read the full article

Past exam of the computer science course of the University of Oxford / 2018 / Algorithms / 1 / b / Solution 2026-10-31

 View more

First perform splaying on the key to be deleted, making its node the root of a tree. Delete that root, leaving left and right subtrees

L, R

. If either is empty, return the other. Otherwise find the maximum key

m

L

by following right-child references, and perform splaying on

m

within

L

. This makes

m

the root of

L

with an empty right subtree. Attach

R

there. The result is the original splay tree with exactly the selected key removed. An unsuccessful lookup leaves the represented set unchanged.

For algorithm correctness, all keys of

L

are smaller than the deleted key, and all keys of

R

are larger. Splaying preserves the binary search tree property by the permitted assumption. Since

m

is the maximum of

L

, it has no larger key within

L

; since every key of

R

exceeds

m

, attaching

R

as its right subtree preserves every ordering condition. All remaining keys occur once. This is the join-based deletion of a splay tree.^[ref]

 Read the full article

Past exam of the computer science course of the University of Oxford / 2018 / Algorithms / 1 / d / Solution 2026-10-31

 View more

Use the conventional bottom-up red-black tree insertion: insert a red node by the binary search tree rule, repair a red parent with recolouring or tree rotations, and make the root black. Write

B

and

R

for black and red. The first three insertions give root

3 4_{B}

, with

2 1_{R}

on the left and

5 5_{R}

on the right.

Inserting

40

as the left child of

55

gives a red parent and a red uncle. Recolour

21, 55

black and retain a black root

34

. Inserting

45

then gives the inner configuration

5 5_{B}

–

4 0_{R}

–

4 5_{R}

. A left tree rotation at

40

, followed by a right tree rotation at

55

, produces a subtree rooted at

4 5_{B}

with

4 0_{R}

and

5 5_{R}

beneath it. Finally insert

3 7_{R}

to the left of

4 0_{R}

. Its uncle

5 5_{R}

is red, so recolour

40, 55

black and

45

red. No further repair is required because

45

has black parent

34

The final root is $3 4_{B}$ ; its left child is $2 1_{B}$ and its right child is $4 5_{R}$ . Under $4 5_{R}$ are $4 0_{B}$ on the left and $5 5_{B}$ on the right; $4 0_{B}$ has left child $3 7_{R}$ . All omitted children are black null sentinels. Each root-to-null graph path has two real black nodes, and no red node has a red child.

Figure 1.
The red-black tree after the six insertions, with colours also marked B and R
. **Details**.

 Read the full article

Past exam of the mathematics course of the University of Cambridge / 2006 / ia / Paper 5 / 6 / b / Solution Created 2026-09-24 Updated 2026-10-14

 View more

Represent a binary search tree by:

sml
datatype ('k, 'v) dict = Empty
    | Branch of ('k, 'v) dict * 'k * 'v * ('k, 'v) dict;

Assume the provided lookup d key returns NONE or SOME value, and update d (key, value) returns the updated binary search tree. Traverse the first dictionary, retaining only a key with the same value in the second:

sml
fun intersection equal d1 d2 =
    let
        fun visit Empty result = result
          | visit (Branch (left, key, value, right)) result =
              let
                  val r1 = visit left result
                  val r2 =
                      case lookup d2 key of
                          NONE => r1
                        | SOME other =>
                            if equal (value, other)
                            then update r1 (key, value)
                            else r1
              in
                  visit right r2
              end
    in
        visit d1 Empty
    end;

For equality-type values, call intersection (op =) d1 d2. An explicit value comparison parameter also handles values for which Standard ML does not define built-in equality. This distinguishes absent keys from defined values without reserving a sentinel value.

Every inserted entry belongs to both input dictionaries with the same value, so the result agrees with each. Conversely, each common equal-valued entry is visited in d1, found in d2, and inserted. Any dictionary agreeing with both can contain only those entries. Thus the result is exactly the largest common dictionary, not merely an intersection of key sets. If d1 has

m

entries, lookup height is

h_{2}

, and maximum result-tree height during insertion is

h_{r}

, the time complexity is

O (m (1 + h_{2} + h_{r}))

for constant-cost comparisons. Logarithmic heights require a balancing assumption; an ordinary unbalanced binary search tree can have linear height.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Functional programming, design and analysis of algorithms / 4 / a / Solution 2026-10-31

 View more

An empty constructor and a constructor containing a label and two subtrees give a polymorphic algebraic data type:

data STree a = Empty | Node (STree a) a (STree a)
  deriving (Eq, Show)

The binary search tree invariant is

every left label < x < every right label

at each Node left x right, together with the same invariant recursively in both subtrees. Labels are distinct because the representation is of a set. The declaration itself needs no ordering constraint; operations that compare labels require Ord a in their type signatures.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Functional programming, design and analysis of algorithms / 4 / b / Solution 2026-10-31

 View more

Follow the unique branch in which the new key could belong. At an equal key, keep the existing node so that duplicate insertion does not change the represented set:

insert :: Ord a => a -> STree a -> STree a
insert y Empty = Node Empty y Empty
insert y (Node left x right) =
  case compare y x of
    LT -> Node (insert y left) x right
    EQ -> Node left x right
    GT -> Node left x (insert y right)

The Haskell Ord class supplies the three-way comparison. Each visited nonempty node costs one such comparison; rebuilding a node preserves all untouched subtrees. The inserted key satisfies every comparison along its search path, so it obeys both the local and ancestor binary search tree inequalities.

For height of a binary tree

h

, the worst search costs

Θ (h) comparisons

when it reaches the bottom. With

n

existing nodes, a chain can require

n

comparisons, giving a worst case of

Θ (n)

. Under the standard random-insertion model, distinct keys arrive in a uniformly random order and the expected path length is

Θ (lo g (n + 1))

. Thus the usual average-case answer is

Θ (lo g n)

for growing

n

, but this expectation needs the stated distribution: an arbitrary unbalanced binary search tree has no logarithmic guarantee.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Functional programming, design and analysis of algorithms / 4 / d / Solution 2026-10-31

 View more

Use the empty list for an empty subtree, and join the left result, the current label and the right result:

flatten :: STree a -> [a]
flatten = foldSTree (\left x right -> left ++ (x : right)) []

Thus

flatten (Node l x r) = flatten (l) + + [x] + + flatten (r)

. This is an inorder traversal. By structural induction, each subtree produces its labels in order; the binary search tree invariant places every left label below

x

and every right label above

x

, proving that the whole result is increasing. The definition works for any binary-tree shape, although its result is sorted only when the ordering invariant holds. Repeated list concatenation can give quadratic cost on a left chain; the question asks for a tree fold definition, rather than an optimal traversal implementation.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Functional programming, design and analysis of algorithms / 4 / e / Solution 2026-10-31

 View more

An empty binary search tree has zero nodes; a nonempty node contributes one in addition to the sizes of its two subtrees:

size :: STree a -> Integer
size = foldSTree (\left _ right -> 1 + left + right) 0

The answer is

∣ Empty ∣ = 0, ∣ Node l x r ∣ = 1 + ∣ l ∣ + ∣ r ∣

. The tree fold visits every node once, so this takes

Θ (n)

arithmetic operations for

n

nodes.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Functional programming, design and analysis of algorithms / 4 / f / Solution 2026-10-31

 View more

Count the number of nonempty levels on the longest root-to-leaf branch, taking the empty binary search tree to have depth zero:

depth :: STree a -> Integer
depth = foldSTree (\left _ right -> 1 + max left right) 0

Thus

d (Empty) = 0, d (Node l x r) = 1 + max (d (l), d (r))

. A singleton has depth one under this convention. If height of a binary tree is instead counted in edges, subtract one for a nonempty tree. The complete tree fold takes

Θ (n)

operations.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Functional programming, design and analysis of algorithms / 4 / g / Solution 2026-10-31

 View more

Search as for insertion. Removing a node with at most one nonempty child leaves that child in its place. With two children, use the smallest key in the right subtree as the replacement and remove that occurrence from the right subtree:

delete :: Ord a => a -> STree a -> STree a
delete _ Empty = Empty
delete y (Node left x right) =
  case compare y x of
    LT -> Node (delete y left) x right
    GT -> Node left x (delete y right)
    EQ -> join left right
  where
    -- Join two search trees with every left key below every right key.
    join :: STree a -> STree a -> STree a
    join Empty r = r
    join l Empty = l
    join l r = let (smallest, rest) = takeMin r
               in Node l smallest rest

-- Precondition: the input tree is nonempty.
takeMin :: STree a -> (a, STree a)
takeMin Empty = error "takeMin: empty tree"
takeMin (Node Empty x right) = (x, right)
takeMin (Node left x right) =
  let (smallest, rest) = takeMin left
  in (smallest, Node rest x right)

The call to takeMin occurs only after both empty cases have been excluded. Its structural recursion follows left children until it reaches the minimum label and rebuilds the path with that occurrence removed.

For a matching label

x

and successor

s

, all left labels are below

x < s

, while every label remaining on the right is strictly above

s

. Thus replacing

x

s

preserves the binary search tree invariant. Every other branch preserves the invariant by structural induction. The resulting set is exactly

keys (delete y t) = keys (t) ∖ {y} .

(1)

Whether the key is absent or present, untouched subtrees can be shared. The search path followed by the successor path uses

O (h)

time and fresh nodes for original height of a binary tree

h

, so the worst case is

O (n)

without balancing. This is persistent binary search tree deletion: the original value remains available.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Imperative programming / 5 / b / Solution 2026-10-31

 View more

The representation invariant says that root is either null or the root of a finite, acyclic binary search tree, with no software object shared between different child subtrees. Every reachable entry has a non-null word and a strictly positive frequency. For each entry

t

, every word in its entire left subtree is strictly less than t.word, and every word in its entire right subtree is strictly greater. This is an inherited ordering condition on all descendants, rather than merely a comparison with immediate children. It implies that each distinct word has exactly one entry. The empty initial state satisfies it.

The abstraction function is the finite multiset assigning each stored word its positive count and assigning all other words zero. Frequencies and their increments must fit in Int; the implementation below explicitly rejects an increment at its representational limit instead of silently violating positivity through integer overflow.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Imperative programming / 5 / c / Solution 2026-10-31

 View more

Return the new root of the affected subtree, assigning that result back to the parent's child reference:

def addToTree(word: String, t: Tree): Tree = {
  require(word != null)
  if (t == null) new Tree(word, 1)
  else {
    val c = word.compareTo(t.word)
    if (c < 0) t.left = addToTree(word, t.left)
    else if (c > 0) t.right = addToTree(word, t.right)
    else {
      require(t.count < Int.MaxValue)
      t.count += 1
    }
    t
  }
}
// Updating the whole structure uses: root = addToTree(word, root)

Assume the input binary search tree satisfies part (b)'s representation invariant and, if the key already occurs, its count can be incremented. Structural induction proves the postcondition. For an empty subtree, the fresh entry represents one occurrence. Otherwise the word comparison identifies the only possible child subtree containing the word. The recursive call adds exactly one occurrence there, preserving the inherited strict bounds; in the equal case only the count changes. The number of entries in the current subtree strictly decreases in each recursive call, proving algorithm termination. The returned binary search tree represents the old multiset plus one occurrence of word. With height

h

, at most

h + 1

comparisons are made; without balancing this can be linear in the number of words. Actual comparison work also depends on the compared string data type lengths.

 Read the full article