Trees Notes

Part 1: What is a tree?

Trees in Java are a type of nonlinear data structure in which data is organized hierarchically rather than in a set order.

  • Nodes are elements stored in a tree.

  • Edges connect nodes to each other.

  • Parents are the nodes above another node that connect to a node beneath them.

  • Children are the nodes bellow another node.

  • A root is a node with no parents.

  • A leaf is a node with no children.

  • An internal node is a node with both parents and children.

  • Nodes with the same parent are siblings.

Example 1: A family tree. A Java Tree is just a family tree where everyone only has one parent instead of two.

Example 2: A decision tree where each question leads to another question and eventually an answer

As you can see, trees are defined by related terms rather than indexes.

A path through the tree is any route from a parent node to a leaf. Nodes at the top of the path and ancestors and at the bottom of the path are descendants.

  • The height is the longest path from root to leaf.

In this case, A is a root node. D, E, F, and G are leaves. B and C are internal nodes. B is the parent and D, E, and F, and all of those are descendants of A. We can create a path from A, to B, to D. The height of this tree is 3.

The order of the tree is the number of children a node can have. This specific tree is a general tree, because nodes can have any number of children. If there were a limit on the number of children a node can have, it would be considered an n-ary tree (Example: binary, trinary, etc.). The most common and important type of tree is a binary tree.

This tree is also balanced, meaning all leaves are withing one level of each other. For comparison, the tree below is NOT balanced because the leaves are spread out across three levels.

A tree is complete if it is balanced and all leaves on the bottom level are on the far-left side of the tree. Tree #1 is complete, tree #2 is not.


Part 2: Implementing trees

There are many ways to implement trees. The most obvious and simple is a linked list where each node has one parent and multiple children.

It IS possible to implement a tree with an array. This is easiest with a binary tree. The root goes at position 0. Its left child goes at position (2n + 1), where n is the position of the parent, and its right child goes at position (2 * (n + 1)).

The other method of implementing trees with arrays would use a similar method to the linked list method. Each element is added as they are created to an array. The nodes, rather than containing a reference to the next element, contain a reference to the index of the next element. This method requires the implementation of a freelist when items are deleted, so that new elements are added to the first available index rather than the end of the list.


Part 3: Traversing trees

There are four main kinds of tree traversal:

Preorder Traversal:

Start at the root. Visit the left node and all of its children. Then visit the right node and all of its children.

Inorder Traversal:

Start at the far-left leaf. Go to its parent and traverse all of their right children. Then go back to the parent and repeat.

Postorder Traversal:

The same as preorder traversal but we don’t look at the root until looking at all of its children.

Level-Order Traversal:

Visit each level left to right. Most logical visual, most confusing to program.


Part 4: Binary tree ADT

  • getRoot - Object - Get the root of the tree

  • isEmpty - Boolean - Check if the tree has any items

  • size - Integer - Get the number of nodes in the tree

  • contains - Boolean - Traverse a tree and check if it contains a certain object

  • toString - String - A representation of the tree

  • Contains iterators for all four methods