Logo

Programming-Idioms

  • Python
  • Scala

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.

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)

ADT style
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
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...
< >
programming-idioms.org