Skip to content

Instantly share code, notes, and snippets.

Forked from iestynpryce/
Created Mar 19, 2018
What would you like to do?
An implementation of a Binary Sort Tree in Bash. Object-like behaviour has been faked using eval. Remember that eval in shell scripting can be evil.
#!/bin/sh -efu
# Binary search tree is of the form:
# 10
# / \
# / \
# 4 16
# / \ /
# 1 7 12
# Print the binary search tree by doing a recursive call on each node.
# Call the left node, print the value of the current node, call the right node.
# Cost is O(N), where N is the number of elements in the tree, as we have to
# visit each node once.
print_binary_search_tree() {
local node="$*";
# Test is the node id is blank, if so return
if [ "${node}xxx" = "xxx" ]; then
print_binary_search_tree $(eval ${node}_getLeftChild)
echo $(${node}_getValue)
print_binary_search_tree $(eval ${node}_getRightChild)
### Utility functions to generate a BST ###
# Define set 'methods'
set_node_left() {
eval "${1}_getLeftChild() { echo "${2:-}"; }"
set_node_right() {
eval "${1}_getRightChild() { echo "${2:-}"; }"
set_node_value() {
eval "${1}_getValue() { echo "${2:-}"; }"
# Generate unique id:
gen_uid() {
# prefix 'id' to the uid generated to guarentee
# it starts with chars, and hence will work as a
# bash variable
if [ -f "/proc/sys/kernel/random/uuid" ]; then
echo "id$(tr -d '-' < /proc/sys/kernel/random/uuid)";
echo "id$(uuidgen|tr -d '-')";
# Generates a new node 'object'
new_node() {
local node_id="$1";
local value="$2";
local left="${3:-}";
local right="${4:-}";
eval "${node_id}set='set'";
eval "set_node_value $node_id $value";
eval "set_node_left $node_id $right";
eval "set_node_right $node_id $right";
# Inserts a value into a tree with a root node with identifier '$id'.
# If the node, hence the tree does not exist it creates it.
# If the root node is at the either end of the list you'll reach the
# worst case complexity of O(N), where N is the number of elements in
# the tree. (Average case will be 0(logN).)
tree_insert() {
local id="$1"
local value="$2";
# If id does not exist, create it
if [ -z "$(eval "echo \${${id}set:-}")" ]; then
eval "new_node $id $value";
# If id exists and the value inserted is less than or equal to
# the id's node's value.
# - Go down the left branch
elif [ $value -le $(${id}_getValue) ]; then
# Go down to an existing left node if it exists, otherwise
# create it.
if [ "$(eval ${id}_getLeftChild)xxx" != "xxx" ]; then
tree_insert $(eval ${id}_getLeftChild) $value
local uid=$(gen_uid);
tree_insert $uid $value;
set_node_left $id $uid;
# Else go down the right branch as the value inserted is larger
# than the id node's value.
# Go down the right node if it exists, else create it
if [ "$(eval ${id}_getRightChild)xxx" != "xxx" ]; then
tree_insert $(eval ${id}_getRightChild) $value
local uid=$(gen_uid);
tree_insert $uid $value;
set_node_right $id $uid;
# Insert an unsorted list of numbers into a binary search tree
for i in 10 4 16 1 7 12; do
tree_insert bst $i;
# Print the binary search tree out in order
print_binary_search_tree bst
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment