# Overview of the Tree ADT

18/October/2014 by Valkryst, Updated 29/June/2017

The following post is derived from notes taken while reading through this textbook.

The running-time of all of these methods assumes that the tree is using a linked structure.

## Common Methods for Trees:

**root()**- Return the tree's root-node. This is an O(1) operation.**size()**- Return the number of nodes in the tree. This is an O(1) operation.**isEmpty()**- Return whether-or-not the tree is empty. This is an O(1) operation.**iterator()**- Return an iterator of all the elements stored at nodes of the tree. This is an O(n) operation.**positions()**- Return an iterable collection of all the nodes of the tree. This is an O(n) operation.**replace(Node n, Node m)**- Save node n, replace node n with node m, and then return the saved node. This is an O(1) operation.

## Common Methods for Tree Nodes:

**element()**- Return the object stored in this node. This is an O(1) operation.**parent(Node n)**- Return the parent of the specified node. This is an O(1) operation.**children(Node n)**- Return an iterable collection containing the children of node n. This is an O(numberOfChildrenOfNodeN) operation.**isInternal(Node n)**- Return whether-or-not the specified node is internal. This is an O(1) operation.**isExternal(Node n)**- Return whether-or-not the specified node is external. This is an O(1) operation.**isRoot(Node n)**- Return whether-or-not the specified node is the root-node of the tree. This is an O(1) operation.

**Root**- The root-node is the red node. This is because every other node branches from it.**Edge**- The blue line is an edge. An edge is a connection between two nodes.**Path**- A path is a sequence of nodes and edges that connect one node to another. The red node has a path to the orange node by going along the blue edge, then through the purple node, then along another edge before reaching the orange node.**Leaf/External Node**- The orange, yellow, and green nodes are all leaf nodes because they have no children.**Parent**- A parent is a node who has at-least one child. The red and purple nodes are parents because they have children.**Child**- A child is a node who has a parent. The orange and yellow nodes are children of their parent, the purple node. The purple and green nodes are children of their parent, the red node.**Siblings**- Children who share the same parent are siblings. The orange and yellow nodes are siblings because they share the purple node as a parent. The purple and green nodes are siblings because they share the red node as a parent.

The example image provided is not the *only* configuration for a tree. The nodes
of a tree can contain as many children as you want, but there can only be one parent
for each child.

## Additional Information:

- For an implementation of a Tree in Java, you can use this and this together. These two classes do not include all of the methods mentioned in this post, but they are good for a general-purpose tree.
- Notable pages from the textbook:
- Page 281 - The formal definition of a Tree is at the bottom of the page.
- Page 286 - Some notes on using a linked structure with a tree.