What is a Tree?

A node with two link fields can also be used to build a hierarchical structure such as a binary tree, and a node with more link fields can be used to build a generic tree. A tree is a linked data structure with a distinct starting node (which could be null) in which the connections move in one direction and spread out so that there is a single parent-to-many-child relationship, without cycles. Here is an example of a tree, alongside a “real” tree to show the resemblance:

Note: no trees were harmed in the writing of this chapter.

Tree Terminology

Root – the starting node, thought of as the top of the (upside-down) tree. In the example, A is the root.

Parent – every node in a tree, except the root, has exactly one parent. The parent is the node just above. A parent can have many children (siblings). In the example, A is the parent of B, C, and D. B, C, and D are siblings.

Child – a node right below, one step away from the parent. In the example, B is a child of A and K is a child of F

Internal node – a node with at least one child. The internal nodes of the example are A. B. C. and F.

External node, also called a leaf – a node without any children. The leaves of the example are E, I, J, K, G, H, and D.

Level or depth of a node – The root is at level 0. The level of other nodes is determined by how many steps a node is away from the root. For example, node E is at level 2, node J is at level 3, and node C is at level 1.

Height of a tree – the maximum depth of any node in the tree. In our example, the height is 3.

Ancestor – The ancestors of a node include that node, the parent of that node, the grandparent of that node, and so on up to the root. The ancestors of a node contain every node from that node to the root, inclusive. In the example, A is an ancestor of every node in the tree, including A itself.

Proper Ancestor – An ancestor that is not the node itself. For example, A and B are ancestors of B, but only A is a proper ancestor of B.

Descendant – The descendants of a node include that node, the children of that node, the grandchildren of that node, and so on until the bottom of the tree is reached. The descendants of a node is every node from that node to the leaves that may be reached, inclusive. In the example, every node in the tree is a descendant of A, including A itself.

Proper Descendant – A descendant that is not the node itself. For example, F, I, J, and K are descendants of F, but only I, J, and K are proper descendants of F.

Path - The nodes and connections between two nodes, in a downward direction only. For example, there is no path from C to D, nor is there a path from C to A. There is a path from B to J and that path is B-F-J.

Binary Tree – A tree where each node has two link fields (a left child and a right child). Each link field may point to another node or to null so in a binary tree each node has zero, one or two children. The example tree is not a binary tree since A and F have three children.

Subtree – a tree consisting of a node and its descendants. For example, the nodes C, G and H with their connections form a subtree. The node J alone is a subtree. The node B alone is not a subtree. The nodes B, E, F, I, J, and K with their connections form a subtree. A tree may be defined recursively as a tree is empty or a tree has a root plus the root’s subtrees, one subtree per child of the root.

Visit – Doing work at a particular node of a tree. The work may be printing the node, manipulating the information in the node, using the information somehow, etc.

Traversal – A way of moving through a tree. We always need to start at the root, and progress from the root by following the links.

Practice Questions

1. Determine whether each of the following is a tree, and if a tree, identify the root and leaves and whether it is a binary tree.
   a.

   

   b.

   

   c.

   

   d.

   

   e.

   

   f.

   

   g.

   

   
   
   

2. Given the following binary tree:

   

   a. Which nodes are the ancestors of grapefruit? proper ancestors?
   b. Which nodes are the descendants of lemon? proper descendants?
   c. Which node is the parent of lemon?
   d. Which node is the parent of canteloupe?
   e. Which nodes are siblings to kiwi?
   f. Which nodes are children of grapefruit?
   g. Identify the leaves.
   h. Give the path from the root to canteloupe. i. Give the path from banana to lemon. j. Give the path from kiwi to apple. k. What is the height of the tree? l. What is the depth of watermelon?

To Solutions