Level-Order Traversal

Visit a tree breadth-first with a queue.

Algorithm

The canonical tree is 4(2(1,3),6(5,7)), so this Bash DSA implementation can be compared directly with the rest of the DSA track.

level order Level-order traversal uses a queue to visit shallower nodes first.

Basic Implementation

                            basic.sh
                        
Replay: real traced execution (multi-file project)

                            #!/usr/bin/env bash
declare -A val left right
new_node() { local id=$1 value=$2 l=${3:-0} r=${4:-0}; val[$id]=$value; left[$id]=$l; right[$id]=$r; }
render() {
  local id=$1
  if [[ "$id" == "0" || -z "$id" ]]; then printf "_"; return; fi
  if [[ "${left[$id]}" == "0" && "${right[$id]}" == "0" ]]; then printf "%s" "${val[$id]}"; return; fi
  printf "%s(" "${val[$id]}"; render "${left[$id]}"; printf ","; render "${right[$id]}"; printf ")"
}
sample_tree() {
  new_node 1 1; new_node 3 3; new_node 2 2 1 3
  new_node 5 5; new_node 7 7; new_node 6 6 5 7
  new_node 4 4 2 6
}
list_string() {
  local joined=""
  for value in "$@"; do
    [[ -n "$joined" ]] && joined+=", "
    joined+="$value"
  done
  printf '[%s]' "$joined"
}
sample_tree
queue=(4); output=(); front=0
while (( front < ${#queue[@]} )); do id=${queue[$front]}; ((front++)); output+=("${val[$id]}"); [[ "${left[$id]}" != "0" ]] && queue+=("${left[$id]}"); [[ "${right[$id]}" != "0" ]] && queue+=("${right[$id]}"); done
list_string "${output[@]}"; echo

                        
1tree ← 4(2(1,3),6(5,7)), queue ← [4]1#!/usr/bin/env bash2declare -A val left right⋯values this step4(2(1,3),6(5,7))tree[4]queue
2output ← [4], queue ← [2, 6]⋯23sample_tree24queue=(4); output=(); front=025while (( front < ${#queue[@]} )); do id=${queue[$front]}; ((front++)); output+=("${val[$id]}"); [[ "${left[$id]}" != "0" ]] && queue+=("${left[$id]}"); [[ "${right[$id]}" != "0" ]] && queue+=("${right[$id]}"); done⋯values this step[4]output[2, 6]queue4dequeued
3output ← [4, 2], queue ← [6, 1, 3]⋯23sample_tree24queue=(4); output=(); front=025while (( front < ${#queue[@]} )); do id=${queue[$front]}; ((front++)); output+=("${val[$id]}"); [[ "${left[$id]}" != "0" ]] && queue+=("${left[$id]}"); [[ "${right[$id]}" != "0" ]] && queue+=("${right[$id]}"); done⋯values this step[4, 2]output[6, 1, 3]queue2dequeued
4output ← [4, 2, 6], queue ← [1, 3, 5, 7]⋯23sample_tree24queue=(4); output=(); front=025while (( front < ${#queue[@]} )); do id=${queue[$front]}; ((front++)); output+=("${val[$id]}"); [[ "${left[$id]}" != "0" ]] && queue+=("${left[$id]}"); [[ "${right[$id]}" != "0" ]] && queue+=("${right[$id]}"); done⋯values this step[4, 2, 6]output[1, 3, 5, 7]queue6dequeued
5output ← [4, 2, 6, 1], queue ← [3, 5, 7]⋯23sample_tree24queue=(4); output=(); front=025while (( front < ${#queue[@]} )); do id=${queue[$front]}; ((front++)); output+=("${val[$id]}"); [[ "${left[$id]}" != "0" ]] && queue+=("${left[$id]}"); [[ "${right[$id]}" != "0" ]] && queue+=("${right[$id]}"); done⋯values this step[4, 2, 6, 1]output[3, 5, 7]queue1dequeued
6output ← [4, 2, 6, 1, 3], queue ← [5, 7]⋯23sample_tree24queue=(4); output=(); front=025while (( front < ${#queue[@]} )); do id=${queue[$front]}; ((front++)); output+=("${val[$id]}"); [[ "${left[$id]}" != "0" ]] && queue+=("${left[$id]}"); [[ "${right[$id]}" != "0" ]] && queue+=("${right[$id]}"); done⋯values this step[4, 2, 6, 1, 3]output[5, 7]queue3dequeued
7output ← [4, 2, 6, 1, 3, 5], queue ← [7]⋯23sample_tree24queue=(4); output=(); front=025while (( front < ${#queue[@]} )); do id=${queue[$front]}; ((front++)); output+=("${val[$id]}"); [[ "${left[$id]}" != "0" ]] && queue+=("${left[$id]}"); [[ "${right[$id]}" != "0" ]] && queue+=("${right[$id]}"); done⋯values this step[4, 2, 6, 1, 3, 5]output[7]queue5dequeued
8output ← [4, 2, 6, 1, 3, 5, 7], queue ← []⋯23sample_tree24queue=(4); output=(); front=025while (( front < ${#queue[@]} )); do id=${queue[$front]}; ((front++)); output+=("${val[$id]}"); [[ "${left[$id]}" != "0" ]] && queue+=("${left[$id]}"); [[ "${right[$id]}" != "0" ]] && queue+=("${right[$id]}"); done⋯values this step[4, 2, 6, 1, 3, 5, 7]output[]queue7dequeued
9if [[ "$id" == "0" || -z "$id" ]]; then printf "_"; return; fi⋯5local id=$16if [[ "$id" == "0" || -z "$id" ]]; then printf "_"; return; fi7if [[ "${left[$id]}" == "0" && "${right[$id]}" == "0" ]]; then printf "%s" "${val[$id]}"; return; fi⋯values this step[4, 2, 6, 1, 3, 5, 7]output

Complexity

Time: O(n)
Space: O(w) queue space

Implementation notes

Render tree structure explicitly instead of printing node objects.
The replay highlights the node, traversal state, queue, path, or search cursor that changes at each step.