Braun tree

A Braun tree is a binary tree balanced as tightly as possible: at every node the size of the left subtree is equal to that of the right one or one greater^[1][3]. Because the condition fixes the shape for each size, there is never anything to rebalance, and a Braun tree of $n$ nodes has height $\lfloor {\log }_{2}n\rfloor +1$. Its main use is as a functional flexible array, a sequence that supports indexing and growth at the front in $O(\log n)$ time^[2][4].

Element 0 is at the root. The remaining elements are dealt alternately to the two subtrees, the odd indices to the left and the even ones to the right, recursively:

Dealing alternately is what keeps the sizes within one of each other.

Adding an element at the front shifts every index up by one, which moves the old odd elements to even positions and the even ones to odd. cons therefore puts the new element at the root, conses the old root onto the old right subtree to make the new left one, and makes the old left subtree the new right one. Removing the front element reverses this. Both follow one path, so they take $O(\log n)$ time^[3].

(* A Braun tree: at every node the left subtree has the same size as the
   right one, or one more. Element 0 is the root, odd indices are in the
   left subtree and even ones in the right. *)
type 'a t = Empty | Node of 'a * 'a t * 'a t
 
let rec cons x = function
  | Empty -> Node (x, Empty, Empty)
  | Node (y, l, r) -> Node (x, cons y r, l)
 
let rec uncons = function
  | Empty -> None
  | Node (x, l, r) -> (
      match uncons l with
      | None -> Some (x, Empty)
      | Some (y, l') -> Some (x, Node (y, r, l')))
 
let rec get t i =
  match t with
  | Empty -> invalid_arg "get"
  | Node (x, l, r) ->
      if i = 0 then x else if i mod 2 = 1 then get l ((i - 1) / 2) else get r ((i - 2) / 2)
 
let rec set t i v =
  match t with
  | Empty -> invalid_arg "set"
  | Node (x, l, r) ->
      if i = 0 then Node (v, l, r)
      else if i mod 2 = 1 then Node (x, set l ((i - 1) / 2) v, r)
      else Node (x, l, set r ((i - 2) / 2) v)
 
(* diff t m is size t - m, for a tree of size m or m + 1. *)
let rec diff t m =
  match (t, m) with
  | Empty, 0 -> 0
  | Node _, 0 -> 1
  | Node (_, l, _), m when m mod 2 = 1 -> diff l ((m - 1) / 2)
  | Node (_, _, r), m -> diff r ((m - 2) / 2)
  | Empty, _ -> invalid_arg "diff"
 
(* The right subtree's size determines the left's up to one. *)
let rec size = function
  | Empty -> 0
  | Node (_, l, r) -> let m = size r in 1 + 2 * m + diff l m
 
let of_list l = List.fold_left (fun t x -> cons x t) Empty (List.rev l)

The size is not stored. Given the size $m$ of the right subtree, the left one has $m$ or $m+1$ elements, and diff finds out which by following one path. Okasaki's size runs in $O({\log }^{2}n)$ time this way^[3].

open Braun
 
let rec show = function
  | Empty -> "."
  | Node (x, Empty, Empty) -> string_of_int x
  | Node (x, l, r) -> Printf.sprintf "%d(%s %s)" x (show l) (show r)
 
let rec height = function Empty -> 0 | Node (_, l, r) -> 1 + max (height l) (height r)
 
let rec braun_ok = function
  | Empty -> true
  | Node (_, l, r) -> let d = size l - size r in (d = 0 || d = 1) && braun_ok l && braun_ok r

0(1(3(7 .) 5(9 .)) 2(4(8 .) 6))
get 7 = 7, size = 10
after set: get 7 = 70, old version still 7
uncons: 0, then 1(2(4(8 .) 6) 3(5(9 .) 7))
1,000,000 elements: height 20, balanced true, get 765432 = 765432

A million elements gives height 20, which is $\lfloor {\log }_{2}10^6\rfloor +1$. set copies only the path to the updated element, so the old version still holds the old value.

Building a Braun tree from a list in linear time, and finding its size in less than linear time, are the subjects of Okasaki's paper on Braun trees^[3]. A Braun tree that is heap-ordered instead of indexed is a priority queue with logarithmic insertion and deletion and no balance information to maintain. Braun trees are a common teaching example in verified functional programming, where their simple invariant makes proofs short^[5].

W. Braun and Martin Rem described the trees in a 1983 Eindhoven memorandum on flexible arrays^[1], and Rob Hoogerwoord published the design and its derivation in 1992^[2]. Paulson presented flexible arrays as Braun trees in ML for the Working Programmer^[4], and Okasaki gave linear-time construction and sublinear size in 1997^[3].

• Finger treeA persistent sequence with amortized constant-time access at both ends, and concatenation and splitting in logarithmic time. The ends are kept in buffers of one to four elements, and the middle is a finger tree of 2-3 nodes, one level deeper at each step down the spine.
• Red-black treeA red-black tree is a binary search tree whose nodes are coloured red or black so that no red node has a red child and every path from the root to a leaf passes through the same number of black nodes. The two rules keep the height at most 2 log2(n + 1), so search, insertion and deletion take O(log n) time. Red-black trees are an encoding of 2-3-4 trees as binary trees, and Okasaki's functional version reduces insertion to one rebalancing rule with four cases.
• Leftist heapA leftist heap is a priority queue represented as a heap-ordered binary tree in which, at every node, the right spine of the left child is at least as long as the right spine of the right child. The right spine of the whole tree then has at most log₂(n + 1) nodes, and two heaps can be merged in O(log n) time by merging their right spines like sorted lists. Insertion and deletion of the minimum are special cases of merging. Because merging copies only the right spines, leftist heaps are a standard persistent priority queue in functional languages.

1. [1]W. Braun, M. Rem, “A logarithmic implementation of flexible arrays”, Memorandum MR83/4, Eindhoven University of Technology (1983).
2. [2]R. R. Hoogerwoord, “A logarithmic implementation of flexible arrays”, Mathematics of Program Construction (MPC), LNCS 669 (1992).
3. [3]C. Okasaki, “Three algorithms on Braun trees”, Journal of Functional Programming 7 (1997).
4. [4]L. C. Paulson, ML for the Working Programmer, 2nd ed., ch. 4, Cambridge University Press (1996).
5. [5]T. Nipkow et al., Functional Algorithms, Verified!, ch. “Braun Trees” (2021).

last updated 1 October 2026