Problem Solving with Algorithms and Data Structures using Java: The Interactive Edition

One way to represent a tree is as a list of lists. It is interesting to do so because it provides us with a simple recursive data structure that we can look at and examine directly. In an list of list tree, we will store the value of the root node as the first element of the array. The second element of the array will itself be a list that represents the left subtree. The third element of the array will be another list that represents the right subtree. To illustrate this storage technique, let’s look at an example. Figure 6.5.1 shows a simple tree and the corresponding list implementation.

my_tree = [
    "a",  # root
        ["b",  # left subtree
            ["d", [], []],
            ["e", [], []]
        ],
        ["c",  # right subtree
            ["f", [], []],
            []
        ],
    ]

Notice that we can access subtrees of the list using standard list indexing. The root of the tree is my_tree[0], the left subtree of the root is my_tree[1], and the right subtree is my_tree[2]. Once the tree is constructed, we can access the root and the left and right subtrees. One very nice property of this list of lists approach is that the structure of a list representing a subtree adheres to the structure defined for a tree; the structure itself is recursive! A subtree that has a root value and two empty lists is a leaf node. Another nice feature of the list of lists approach is that it generalizes to a tree that has many subtrees. In the case where the tree is more than a binary tree, another subtree is just another list.

This representation works great in languages like Python that use dynamic typing. In these languages, data types are determined at runtime. This lets you define arrays with different data types for each item, as in this Python list (which is what they call arrays):

my_list = [15, "Python", 37.6, false, ["abc", -27]]

Note that the last item of the list is itself another list, again with heterogeneous data. The preceding representation of an array takes advantage of this. The first item in the list is a string; the other items are lists—different data types.

Unfortunately, Java uses static typing. You have to declare a variable’s data type, and it doesn’t change. Moreover, arrays and ArrayLists cannot have heterogeneous data in them; every element must be of the same data type. There are statically typed languages such as OCaml and Haskell that can specify that a variable can have one of several different types—a “union type”—but, again, Java is not such a language.

Since we don’t want to have to give an introduction to Python, we will have to bid a fond farewell to this representation and proceed to a second representation that is more amenable to implementation in Java: nodes and references.