Lesson 35 of 55
10 mins readRecursive Data Structures: Binary Trees
In Plain English
Recursive data structures define types in terms of themselves. Implement a generic Binary Search Tree (Tree a = Empty | Node a (Tree a) (Tree a)) and search algorithms.
Deep Dive: How It Works
Recursive ADT: data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Show, Eq).
Tree Insertion: insertTree x Empty = Node x Empty Empty; recursively navigate left or right child based on comparison.
Tree Traversal: inOrder Empty = []; inOrder (Node val l r) = inOrder l ++ [val] ++ inOrder r.
Core Rules to Remember
Recursive Type Definitions: Build trees, graphs, and nested AST expressions natively.
Pure Immutable Trees: Path copying allows sharing unchanged tree branches with zero memory overhead.
Live Interactive Example
Hit Run Code to see it liveBinary Search Tree Insertion and Traversal
Python 3.12
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Output Console
Click "Run Code" to view the rendered output.
How it works: inOrder traversal of the BST produces the elements in sorted order.
Your Turn: Micro Challenge
No pressure! Edit the starter code below and test your solution with instant feedback.
Micro Exercise
Construct Singleton Tree Node
- Create `t = Node 42 Empty Empty`.
- Print `"Tree: "` followed by `show t`.
1
2
3
4
5
6
7
8
Sandbox Output
Click "Run & Check" to test your solution.
Finished reading and practicing?
Mark this lesson as completed to update your course progress.