Exploring Binary Trees with Functional Elegance

Hey, folks—who’d have thought I’d be back after such a long hiatus? It’s been weeks since my last post in this awesome community, but I’m thrilled to return with Part 16, diving into the world of Binary Trees. These classic data structures are both powerful and versatile, and today, we’ll craft them in Clojure with all the functional flair you’ve come to expect.

What is a Binary Tree, and Why Should You Care?

A Binary Tree is a hierarchical data structure where each node has at most two children: a left child and a right child. It’s the foundation for things like:

  • Search Trees: Fast lookups with binary search trees (BSTs).
  • Expression Trees: Representing and evaluating mathematical expressions.
  • File Systems: Modeling directory structures.

In OOP languages like Java, binary trees are often mutable, with nodes linked via pointers. In Clojure, we’ll take a different path: immutable nodes, persistent data, and recursive functions. Our implementation will use protocols for behavior and records for structure, ensuring extensibility and clarity—all while staying true to functional programming

Implementing a Binary Tree in Clojure

We’ll define a BinaryTree protocol and implement it with a TreeNode record. Each node will hold a value and optional left/right children. Here’s the code—clean, pure, and ready to shine:

(ns clojure-is-awesome.binary-tree
  (:require [clojure.spec.alpha :as s]
            [clojure.pprint :as pp]))
(defprotocol BinaryTree
  "A protocol for binary tree operations."
  (insert [this value]
    "Inserts a value into the tree. Returns a new tree.")
  (bt-contains? [this value]
    "Checks if a value exists in the tree. Returns a boolean.")
  (inorder [this]
    "Returns a sequence of values in inorder traversal (left-root-right).")
  (height [this]
    "Returns the height of the tree. Returns 0 for an empty tree."))

(defrecord TreeNode [value left right]
  BinaryTree
  (insert [this new-value]
    (cond
      (nil? value) (TreeNode. new-value nil nil)
      (< new-value value) (TreeNode. value (insert left new-value) right)
      (> new-value value) (TreeNode. value left (insert right new-value))
      :else this))
  (bt-contains? [this search-value]
    (cond
      (nil? value) false
      (= search-value value) true
      (< search-value value) (bt-contains? left search-value)
      (> search-value value) (bt-contains? right search-value)))
  (inorder [this]
    (concat (when left (inorder left))
            (when value [value])
            (when right (inorder right))))
  (height [this]
    (if (nil? value)
      0
      (inc (max (height left) (height right))))))

(extend-type nil
  BinaryTree
  (insert [_ value]
    (TreeNode. value nil nil))
  (bt-contains? [_ _]
    false)
  (inorder [_]
    [])
  (height [_]
    0))

(defn create-tree
  "Creates an empty binary tree.
   Returns:
     A TreeNode with nil value and children."
  []
  (TreeNode. nil nil nil))

(s/def ::value any?)
(s/def ::left (s/or :node ::tree :nil nil?))
(s/def ::right (s/or :node ::tree :nil nil?))
(s/def ::tree (s/keys :req-un [::value ::left ::right]))
(s/def ::value any?)
(s/def ::left (s/or :node ::tree :nil nil?))
(s/def ::right (s/or :node ::tree :nil nil?))
(s/def ::tree (s/keys :req-un [::value ::left ::right]))

(def my-tree (-> (create-tree)
                 (insert 5)
                 (insert 3)
                 (insert 7)
                 (insert 1)
                 (insert 9)))

(pp/pprint {:tree my-tree})
;; Test operations
(println "Contains 7?" (bt-contains? my-tree 7))   ;; Contains 7? true
(println "Contains 4?" (bt-contains? my-tree 4))   ;; Contains 4? false
(println "Height:" (height my-tree))            ;; Height: 3
(println "Inorder traversal:")
(pp/pprint (inorder my-tree))                   ;; [1 3 5 7 9]

Practical Use Case: Expression Evaluator

Let’s build an expression tree to evaluate simple arithmetic (e.g., (3 + 5) * 2). We’ll extend our tree with an evaluation function:

(defn evaluate
  "Evaluates an expression tree where nodes are operators or numbers.
   Args:
     tree - A TreeNode representing an expression.
   Returns:
     The computed result."
  [tree]
  (let [{:keys [value left right]} tree]
    (if (nil? value)
      0
      (if (number? value)
        value
        (let [left-val (evaluate left)
              right-val (evaluate right)]
          (case value
            + (+ left-val right-val)
            - (- left-val right-val)
            * (* left-val right-val)
            / (/ left-val right-val)
            (throw (Exception. (str "Unknown operator: " value)))))))))

;; Build an expression tree: (3 + 5) * 2
(def expr-tree (TreeNode. '*
                          (TreeNode. '+ 
                                     (TreeNode. 3 nil nil)
                                     (TreeNode. 5 nil nil))
                          (TreeNode. 2 nil nil)))

(println "Expression tree:")
(pp/pprint {:tree expr-tree})

(println "Result:" (evaluate expr-tree)) ;; Result: 16
(println "Inorder:" (inorder expr-tree)) ;; Inorder: (3 + 5 2 *)

This evaluator handles basic arithmetic, and pprint makes the tree’s structure pop. Note that inorder here reflects the raw traversal—real infix notation would need more work, but you get the idea!

Why This Rocks in Clojure

Our binary tree implementation brings some serious wins:

  • Immutability: Every insert creates a new tree, keeping data safe.
  • Extensibility: The protocol lets us swap in balanced trees later.
  • Recursion: Clojure’s recursive style shines in tree operations.
  • Readability: pprint turns complex structures into visual gold.

Performance-wise, this is an unbalanced BST—O(n) for worst-case operations. For production use, we’d want a self-balancing tree (stay tuned for a future part!).