Converting between recursive / indented tree data structure

Question

To represent a tree, for example:

• root
  • a
    • a.1
    • a.2
  • b

a, one might use the following data structure:

struct TreeNode {
    var name: String
    var children: [TreeNode] = []
}

var rootNode =
    TreeNode(name: "root", children: [
        TreeNode(name: "a", children: [
            TreeNode(name: "a.1"),
            TreeNode(name: "a.2"),
        ]),
        TreeNode(name: "b"),
    ])

b, alternatively an ordered list with an attribute for the indent could be used:

struct FlatTreeNode {
    var indent: Int
    var name: String
}

var tree = [
    FlatTreeNode(indent: 0, name: "root"),
    FlatTreeNode(indent: 1, name: "a"),
    FlatTreeNode(indent: 2, name: "a.1"),
    FlatTreeNode(indent: 2, name: "a.2"),
    FlatTreeNode(indent: 1, name: "b"),
]

Depending on what I want to do with the tree, I found one or the other form easier to work with.

I wondered:

• Are there well-known terms you would use to differentiate between a data structure like a) or b)? (something like recursive vs. flat/indented tree representation?)

• Is there a standard algorithm to convert between those two forms?

Answer 1

A Swift version of flatten + unflatten:

import Foundation

public struct TreeNode<T: Equatable>: Equatable {
    var content: T
    var children: [TreeNode] = []
}

public struct IndentedTreeNode<T: Equatable>: Equatable {
    var indent: Int
    var content: T
}

public func flatten<T>(_ node: TreeNode<T>, indent: Int = 0) -> [IndentedTreeNode<T>] {
    [IndentedTreeNode(indent: indent, content: node.content)] + node.children.flatMap { flatten($0, indent: indent + 1) }
}

public func unflatten<T>(_ list: [IndentedTreeNode<T>]) -> TreeNode<T>? {
    guard let firstNode = list.first?.content else { return nil }
    let remainingNodes = list.dropFirst()

    var root = TreeNode(content: firstNode)
    var lastNodePath = IndexPath()

    for node in remainingNodes {
        let pathToNodeParent = lastNodePath.prefix(max(node.indent, 1) - 1)
        var children = root[pathToNodeParent].children
        children.append(TreeNode(content: node.content))
        root[pathToNodeParent].children = children
        lastNodePath = pathToNodeParent.appending(children.indices.last!)
    }

    return root
}

public extension TreeNode {

    subscript(indexPath: IndexPath) -> TreeNode {
        get {
            if indexPath.isEmpty {
                return self
            } else {
                return self.children[indexPath.first!][indexPath.dropFirst()]
            }
        }
        set {
            if indexPath.isEmpty {
                self = newValue
            } else {
                self.children[indexPath.first!][indexPath.dropFirst()] = newValue
            }
        }
    }

}

Swift package with unit tests: https://github.com/ralfebert/IndentedTree

Answer 2

On nomenclature, I am not aware of any standard description, but I would describe your first as a nested datastructure; the second as a list showing successive indentation.

Here's a Python program that:

1. Defines the first as nested nodes as 2-tuples of name followed by a list of its children (which can be an empty list denoting leaf items).
2. The second format is a list of 2-tuples whose first item is the indentation, second item a name.

The program converts both-ways and compares to show you can round-trip the conversions.

from pprint import pprint as pp

def to_list(node, depth=0, flat=None):
    if flat is None:
        flat = []
    if node:
        flat.append((depth, node[0]))
    for child in node[1]:
        to_list(child, depth + 1, flat)
    return flat

def to_nest(lst, depth=0, level=None):
    if level is None:
        level = []
    while lst:
        d, name = lst[0]
        if d == depth:
            children = []
            level.append((name, children))
            lst.pop(0)
        elif d > depth:  # down
            to_nest(lst, d, children)
        elif d < depth:  # up
            return
    return level[0] if level else None

if __name__ == '__main__':
    print('Start Nest format:')
    nest = ('root', [('a', [('a.1', []), ('a.2', [])]), ('b', [])])
    pp(nest, width=20)

    print('\n... To List format:')
    as_list = to_list(nest)
    pp(as_list, width=20)

    print('\n... To Nest format:')
    as_nest = to_nest(as_list)
    pp(as_nest, width=20)

    assert nest == as_nest

Output:

Start Nest format:
('root',
 [('a',
   [('a.1', []),
    ('a.2', [])]),
  ('b', [])])

... To List format:
[(0, 'root'),
 (1, 'a'),
 (2, 'a.1'),
 (2, 'a.2'),
 (1, 'b')]

... To Nest format:
('root',
 [('a',
   [('a.1', []),
    ('a.2', [])]),
  ('b', [])])

Of course, the datastructures could use namedtuples, but Ichose not to.

Answer 3

In pseudocode, this should do the trick:

// Arguments flatTree and index mussed be passed by ref
Flatten(node, flatTree, index = 0, indent = 0){
    flatTree[index] = FlatTreeNode(node, indent)
    index += 1
    for child of node {
        Flatten(child, flatTree, index, indent+1)
    }
}

// Arguments flatTree and index mussed be passed by ref
Unflatten(flatTree, index = 0){
    indt = Indent(flatTree[index])
    node = TreeNode(flatTree[index])
    index += 1
    while index < len(flatTree) and Indent(flatTree[index]) > indt {
        child = Unflatten(flatTree, index)
        AddChild(node, child)
    }
    return node
}