# Idiom #9 Create a Binary Tree data structure

The structure must be recursive because left child and right child are binary trees too. A node has access to children nodes, but not to its parent.

``````type
generic BinTree<T> = class
Value: T;
Left, Right: BinTree;
end;   ``````
``````type Tree_Node;
type Tree_Node_Access is access Tree_Node;
type Tree_Node is record
Value: Integer;
Left, Right: Tree_Node_Access;
end record;``````
``````struct treenode{
int value;
struct treenode* left;
struct treenode* right;
}``````
``````type treenode =
Node of {
value: int;
left: treenode;
right: treenode
}
| Leaf``````
``````struct binary_tree
{
int data;
binary_tree *left = nullptr, *right = nullptr;
};``````
``````class BinaryTree<T>:IComparable<T>
{
T value;
BinaryTree<T> leftChild;
BinaryTree<T> rightChild;
}``````
``````struct BinaryTree(T)
{
T data;
BinaryTree* left;
BinaryTree* right;
}``````
``````class Node<T> {
final T value;
Node<T> left, right;
Node(this.value, {this.left, this.right});
}``````
``````defmodule BinaryTree do
defstruct data: nil, left: nil, right: nil
end``````
``````-type binary_tree(T) ::
#{ data := T
, left := binary_tree(T)
, right := binary_tree(T)
}.``````
``````type binary_tree
integer :: value
type(binary_tree), allocatable :: left
type(binary_tree), allocatable :: right
end type binary_tree``````
``````type BinTree[L any] struct {
Label       L
Left, Right *BinTree[L]
}``````
``````type BinTree struct {
Label       valueType
Left, Right *BinTree
}
``````
``````class BinTree<T extends Comparable<T>>{
T value
BinTree<T> left
BinTree<T> right
}``````
``````data BT x = BEnd | BNode (BT x) x (BT x)
``````
``````class Node {
constructor (data) {
this.data = data
this.left = null
this.right = null
}
}``````
``````interface Tree<T>{
boolean search(T x);
}
class Nil<T extends Comparable<? super T>> implements Tree<T>{
public boolean search(T x) { return false; }
}
class Node<T extends Comparable<? super T>> implements Tree<T> {
T item;  Tree<T> left; Tree<T> right;
public Node(T i, Tree<T> l, Tree<T> r) {
item=i;  left=l;  right=r; }
public boolean search(T x) {
int cmp = x.compareTo(item);
return cmp==0 || (cmp<0 && left.search(x)) || (cmp>0 && right.search(x));
}``````
``````class BinTree<T extends Comparable<T>>{
T value;
BinTree<T> left;
BinTree<T> right;
}
``````
``````data class Node(
val key: Int,
val left: Node? = null,
val right: Node? = null
)``````
``````(defclass node ()
((value
:initarg :value :initform nil
:accessor node-value)
(left-child
:initarg :left-child :initform nil
:accessor node-left-child)
(right-child
:initarg :right-child :initform nil
:accessor node-right-child)))
``````
``````local function BinTree(v, l, r)
return {
val = v,
left = l,
right = r
}
end``````
``````@interface Node:NSObject
@property id value; // id means any object value
@property Node *left,*right;
@end

// usage like
Node *n=[Node new];
n.value=@1;
n.left=otherNode;
n.right=anotherNode;

// somewhere needed also
@implementation Node @end
``````
``````class BNode
{
public \$data;
public \$lNode;
public \$rNode;

public function __construct(\$item)
{
\$this->data = \$item;
\$this->lNode = null;
\$this->rNode = null;
}
}``````
``````use Moops;
``````
``````class Tree::Binary {
has 'left', is => 'ro', isa => Maybe[InstanceOf['Tree::Binary']];
has 'right', is => 'ro', isa => Maybe[InstanceOf['Tree::Binary']];
has 'val', is => 'ro', isa => Int;
}
my \$t = Tree::Binary->new(
val => 42,
left => Tree::Binary->new(val => 23),
right => Tree::Binary->new(
val => 1729,
right => Tree::Binary->new(val => -1)
)
);
__END__
42
↙    ↘
23     1729
↙  ↘   ↙    ↘
∅    ∅ ∅     -1
``````
``````class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None``````
``````class Node:
def __init__(self, data, left_child, right_child):
self.data = data
self._left_child = left_child
self._right_child = right_child``````
``````Node = Struct.new(:left, :right, :value)
parent = Node.new(Node.new, Node.new)``````
``````struct BinTree<T> {
value: T,
left: Option<Box<BinTree<T>>>,
right: Option<Box<BinTree<T>>>,
}``````
``````case class BinaryTree[T <: Ordered[T]](
value: T,
left: Option[BinaryTree[T]],
right: Option[BinaryTree[T]]
)``````
``````sealed trait Tree[T <: Ordered[T]]:
def search(x: T): Boolean
final case class Nil[T <: Ordered[T]]() extends Tree[T]:
override def search(x: T): Boolean = false
final case class Node[T <: Ordered[T]](
item: T,
left: Tree[T],
right: Tree[T]
) extends Tree[T]:
override def search(other: T): Boolean =
item compare other match
case 0          => true
case n if n < 0 => left.search(other)
case n if n > 0 => right.search(other)``````
``````(define (make-btree value left right)
(cons value (cons left right)))

(define (btree-value bt) (car bt))
``````Object subclass: #TreeNode