Data structures and algorithms · Lesson 21 of 60 · Code lesson, JavaScript or Python · Optional
Trees
A tree is a hierarchy with one root node at the top, and each node can have children below it.
In a binary tree each node has at most two children, called left and right.
In a binary search tree smaller values go left and larger values go right, so visiting left, then the node, then right gives the values in sorted order.
Worked example
In JavaScript, a function that calls itself on node.left and node.right walks the tree one branch at a time.
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
function insert(node, value) {
if (node === null) return new Node(value);
if (value < node.value) node.left = insert(node.left, value);
else node.right = insert(node.right, value);
return node;
}
function inOrder(node) {
if (node === null) return;
inOrder(node.left);
console.log(node.value);
inOrder(node.right);
}
let root = null;
for (const number of [2, 1, 3]) root = insert(root, number);
inOrder(root);Output:
1 2 3
In Python, a function that calls itself on node.left and node.right walks the tree one branch at a time.
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert(node, value):
if node is None:
return Node(value)
if value < node.value:
node.left = insert(node.left, value)
else:
node.right = insert(node.right, value)
return node
def in_order(node):
if node is None:
return
in_order(node.left)
print(node.value)
in_order(node.right)
root = None
for number in [2, 1, 3]:
root = insert(root, number)
in_order(root)Output:
1 2 3
Your turn
The program builds a binary search tree from the numbers it reads, but inOrder only prints the root. Make inOrder visit the left side first, then the node, then the right side, so the numbers print in sorted order.
Your program is checked with these 3 inputs:
Input:
5 3 8 1 4
Expected output:
1 3 4 5 8
Input:
2 1 3
Expected output:
1 2 3
Input:
9
Expected output:
9
Loading your practice…
Preparing your workspace…