A NEW BFS PARENT ARRAY ENCODING OF t-ARY TREES

Abstract

We introduce a new breadth first search (BFS) parent array encoding of trees as integer sequences. The new representation enables the inclusion of parent-children relations in a straightforward way, which is not the case with the existing representations. We also introduce a children array representation for binary trees and a simple algorithm for generating binary trees (including parent-children relations) using the notation. The algorithm can be applied to generate well-formed parenthesis strings in a simple way. Two generalizations to the case of children array representation for  t-ary trees are also given.