Binary Tree Breadth First Traversal in SQL (SQLite version)

binary-tree-breadth-first.sql

/* related to: https://x.com/vikhyatk/status/1873033432705712304 */

-- Setup
DROP TABLE IF EXISTS binary_tree;
CREATE TABLE binary_tree (
    id INTEGER NOT NULL PRIMARY KEY,
    label TEXT NOT NULL,
    left_child  INTEGER INTEGER REFERENCES binary_tree(id),
    right_child INTEGER REFERENCES binary_tree(id)
);

INSERT INTO binary_tree (id, label, left_child, right_child)
VALUES (6, "six", null, null),
       (5, "five", null, null),
       (3, "three", 5, 6),
       (4, "four", null, null),
       (2, "two", 4, null),
       (1, "one", 2, 3);
       
-- Query, assumes node 1 is the root
WITH RECURSIVE cte (id, label, left_child, right_child, level) AS (
    SELECT bt.*, 0 as level
      FROM binary_tree bt
      WHERE id = 1
    UNION ALL
    SELECT bt.*, cte.level + 1
      FROM cte
      JOIN binary_tree bt on bt.id = cte.left_child
    UNION ALL
    SELECT bt.*, cte.level + 1
      FROM cte
      JOIN binary_tree bt on bt.id = cte.right_child
)
SELECT
    level,
    group_concat(label, ', ') AS nodes_at_level
FROM cte
GROUP BY level
ORDER BY level;

/* 

OUTPUT:

+-----+---------------+
|level|nodes_at_level |
+-----+---------------+
|0    |one            |
|1    |two, three     |
|2    |four, five, six|
+-----+---------------+

*/