Logo

Programming-Idioms

  • Python
  • Ruby
  • JS
  • Java
  • Scala
  • Lisp

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.

(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)))
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)

Should also have a place to store the value
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));
 }

don't have room for more
class BinTree<T extends Comparable<T>>{
   T value;
   BinTree<T> left;
   BinTree<T> right;
}

Note that with this design an empty tree is null, and thus is not an instance of BinTree.
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)

ADT style
case class BinaryTree[T <: Ordered[T]](
	value: T,
	left: Option[BinaryTree[T]],
	right: Option[BinaryTree[T]]
)
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;

New implementation...