Trees

Tree

Inorder Traversal

Walk a small binary tree in left-root-right order, collecting node values into an output array. Demonstrates structural recursion with the classic inorder(left); visit; inorder(right) shape.

Algorithm

Canonical input is the tree 4(2(1,3),6(5,7)) built through seven make_node calls. The inorder walk produces [1, 2, 3, 4, 5, 6, 7].

structural recursion For each non-null node: recurse into the left child, append the value, then recurse into the right child. The base case is the `-1` sentinel.
arena of nodes Three parallel arrays — `node_value`, `node_left`, `node_right` — store the tree as integer indices with `-1` as the null sentinel.

Basic Implementation

basic.sh
Replay: real traced execution (multi-file project)
#!/usr/bin/env bash
set -euo pipefail
node_value=()
node_left=()
node_right=()
last_idx=-1

make_node() {
	local value=$1
	local left=$2
	local right=$3
	local idx=${#node_value[@]}
	node_value[idx]=$value
	node_left[idx]=$left
	node_right[idx]=$right
	last_idx=$idx
}

output=()
inorder() {
	local node=$1
	if [ "$node" -eq -1 ]; then
		return
	fi
	inorder "${node_left[node]}"
	output+=("${node_value[node]}")
	inorder "${node_right[node]}"
}

make_node 1 -1 -1;    n1=$last_idx
make_node 3 -1 -1;    n3=$last_idx
make_node 2 "$n1" "$n3"; n2=$last_idx
make_node 5 -1 -1;    n5=$last_idx
make_node 7 -1 -1;    n7=$last_idx
make_node 6 "$n5" "$n7"; n6=$last_idx
make_node 4 "$n2" "$n6"; root=$last_idx

inorder "$root"

printf '['
sep=''
for v in "${output[@]}"; do
	printf '%s%d' "$sep" "$v"
	sep=', '
done
printf ']\n'

  1. output ← [], tree ← 4(2(1,3),6(5,7))

    36make_node 4 "$n2" "$n6"; root=$last_idx3738inorder "$root"
    values this step[]output4(2(1,3),6(5,7))tree

  2. output ← [1]

    24fi25inorder "${node_left[node]}"26output+=("${node_value[node]}")
    values this step[] → [1]output

  3. output ← [1, 2]

    24fi25inorder "${node_left[node]}"26output+=("${node_value[node]}")
    values this step[1] → [1, 2]output

  4. output ← [1, 2, 3]

    24fi25inorder "${node_left[node]}"26output+=("${node_value[node]}")
    values this step[1, 2] → [1, 2, 3]output

  5. output ← [1, 2, 3, 4]

    24fi25inorder "${node_left[node]}"26output+=("${node_value[node]}")
    values this step[1, 2, 3] → [1, 2, 3, 4]output

  6. output ← [1, 2, 3, 4, 5]

    24fi25inorder "${node_left[node]}"26output+=("${node_value[node]}")
    values this step[1, 2, 3, 4] → [1, 2, 3, 4, 5]output

  7. output ← [1, 2, 3, 4, 5, 6]

    24fi25inorder "${node_left[node]}"26output+=("${node_value[node]}")
    values this step[1, 2, 3, 4, 5] → [1, 2, 3, 4, 5, 6]output

  8. output ← [1, 2, 3, 4, 5, 6, 7]

    24fi25inorder "${node_left[node]}"26output+=("${node_value[node]}")
    values this step[1, 2, 3, 4, 5, 6] → [1, 2, 3, 4, 5, 6, 7]output

  9. stdout ← [1, 2, 3, 4, 5, 6, 7]

    44	sep=', '45done46printf ']\n'
    values this step[1, 2, 3, 4, 5, 6, 7]stdout[1, 2, 3, 4, 5, 6, 7]output

Complexity

  • Time: O(n)
  • Space: O(h) call stack where h is the tree height

Implementation notes

  • Bash: parallel arrays node_value, node_left, node_right indexed by integer (with -1 as the sentinel) keep the structural moves visible. Recursion uses the natural function-call stack; local variables shadow the recursive frames.
  • make_node mutates the arena globals and reports the new node's index through last_idx, the same pattern used in linked-list-reverse. This avoids the subshell trap of idx=$(make_node ...) discarding the array mutation.
  • The replay records each visit frame as visit node(v): output+=(v) and shows the running output array.