Skip to main content

Posts about Binary trees

RSS feed (Binary trees, en)

Proofs of "flatten (mirror a) = reverse (flatten a)"

Discrete Structures/Binary trees

The tree corresponding to

    3
   / \
  2   4
 / \
1   5

can be represented by the term

Node 3 (Node 2 (Leaf 1) (Leaf 5)) (Leaf 4)

using the datatype defined by

   inductive Tree' (α : Type) : Type
     | Leaf : α → Tree' α
     | Node : α → Tree' α → Tree' α → Tree' α

The mirror image of the previous tree is

  3
 / \
4   2
   / \
  5   1

and the list obtained by flattening it (traversing it in infix order) is

[4, 3, 5, 2, 1]

The definition of the function that calculates the mirror image is

   def mirror : Tree' α → Tree' α
     | Leaf x     => Leaf x
     | Node x l r => Node x (mirror r) (mirror l)

and the one that flattens the tree is

   def flatten : Tree' α → List α
     | Leaf x     => [x]
     | Node x l r => (flatten l) ++ [x] ++ (flatten r)

Prove that

   flatten (mirror a) = reverse (flatten a)

To do this, complete the following Lean4 theory:

import Mathlib.Tactic

open List

variable {α : Type}

set_option pp.fieldNotation false

inductive Tree' (α : Type) : Type
  | Leaf : α → Tree' α
  | Node : α → Tree' α → Tree' α → Tree' α

namespace Tree'

variable (a l r : Tree' α)
variable (x : α)

def mirror : Tree' α → Tree' α
  | Leaf x     => Leaf x
  | Node x l r => Node x (mirror r) (mirror l)

def flatten : Tree' α → List α
  | Leaf x     => [x]
  | Node x l r => (flatten l) ++ [x] ++ (flatten r)

example :
  flatten (mirror a) = reverse (flatten a) :=
by sorry

Read more…

Proofs that the mirror function of binary trees is involutive

Discrete Structures/Binary trees

The tree corresponding to

    3
   / \
  2   4
 / \
1   5

can be represented by the term

Node 3 (Node 2 (Leaf 1) (Leaf 5)) (Leaf 4)

using the datatype defined by

   inductive Tree' (α : Type) : Type
     | Leaf : α → Tree' α
     | Node : α → Tree' α → Tree' α → Tree' α

The mirror image of the previous tree is

  3
 / \
4   2
   / \
  5   1

whose term is

Node 3 (Leaf 4) (Node 2 (Leaf 5) (Leaf 1))

The definition of the function that calculates the mirror image is

   def mirror : Tree' α → Tree' α
     | (Leaf x)     => Leaf x
     | (Node x l r) => Node x (mirror r) (mirror l)

Prove that the mirror function is involutive; that is,

   mirror (mirror a) = a

To do this, complete the following Lean4 theory:

import Mathlib.Tactic

variable {α : Type}

set_option pp.fieldNotation false

inductive Tree' (α : Type) : Type
  | Leaf : α → Tree' α
  | Node : α → Tree' α → Tree' α → Tree' α

namespace Tree'

variable (a l r : Tree' α)
variable (x : α)

def mirror : Tree' α → Tree' α
  | (Leaf x)     => Leaf x
  | (Node x l r) => Node x (mirror r) (mirror l)

example :
  mirror (mirror a) = a :=
by sorry

end Tree'

Read more…