Tree

Course No.: 0714 09 CSE 2151, Course Title: Data Structures and Algorithms
Electronics and Communication Engineering Discipline, Khulna University, Khulna
Md. Farhan Sadique
Email: [email protected]
This lecture is not a study material. Use this lecture as an outline. Follow the outline to study from the mentioned sources
after each section header. The sections of this lecture have been prepared from the mentioned sources.

1. General Trees (Goodrich et al.: 8.1, 8.1.1, 8.1.3)

Tree structures are indeed a breakthrough in data organization, for they allow us to implement a host of
algorithms much faster than when using linear data structures, such as arrays or linked lists. The relationships
in a tree are hierarchical, with some objects being “above” and some “below” others.

Formally, we define a tree T as a set of nodes storing elements such that the nodes have a parent-child
relationship that satisfies the following properties:
• If T is nonempty, it has a special node, called the root of T, that has no parent.
• Each node v of T different from the root has a unique parent node w; every node with parent w is a
child of w.
Two nodes that are children of the same parent are siblings. A node v is external if v has no children. A node
v is internal if it has one or more children. External nodes are also known as leaves.
An edge of tree T is a pair of nodes (u, v) such that u is the parent of v, or vice versa. A path of T is a sequence
of nodes such that any two consecutive nodes in the sequence form an edge.
A tree is ordered if there is a meaningful linear order among the children of each node; that is, we purposefully
identify the children of a node as being the first, second, third, and so on. Such an order is usually visualized
by arranging siblings left to right, according to their order.
Data Structures and Algorithms – Lecture 6 Md. Farhan Sadique

Let p be a position within tree T. The depth of p is the number of ancestors of p, other than p itself. We next
define the height of a tree to be equal to the maximum of the depths of its positions (or zero, if the tree is
empty).
2. Binary Trees (Goodrich et al.: 8.2, https://www.geeksforgeeks.org/complete-binary-tree/)
A binary tree is an ordered tree with the following properties:
• Every node has at most two children.
• Each child node is labeled as being either a left child or a right child.
• A left child precedes a right child in the order of children of a node.
The subtree rooted at a left or right child of an internal node v is called a left subtree or right subtree,
respectively, of v. A binary tree is proper if each node has either zero or two children. Some people also refer
to such trees as being full binary trees. Thus, in a proper binary tree, every internal node has exactly two
children. A binary tree that is not proper is improper. A complete binary tree is a special type of binary tree
where all the levels of the tree are filled completely except the lowest level nodes which are filled from as left
as possible.

2
Data Structures and Algorithms – Lecture 6 Md. Farhan Sadique
3. Implementing Binary Trees (Goodrich et al.: 8.3.1)
A natural way to realize a binary tree T is to use a linked structure.

• addRoot(e): Creates a root for an empty tree, storing e as the element, and returns the root.
• addLeft(p, e): Creates a left child of node p, storing element e, and returns the new node.
• addRight(p, e): Creates a right child of node p, storing element e, and returns the new node.
• set(p, e): Replaces the element stored at node p with element e, and returns the updated node.
• attach(p, T1, T2): Attaches the internal structure of trees T1 and T2 as the respective left and right
subtrees of leaf node p and resets T1 and T2 to empty trees.
• remove(p): Removes the node p, replacing it with its child (if any), and returns the node that is now at
the position of removed node p.

3
Data Structures and Algorithms – Lecture 6 Md. Farhan Sadique

Fig. Node class.

4
Data Structures and Algorithms – Lecture 6 Md. Farhan Sadique

5
Data Structures and Algorithms – Lecture 6 Md. Farhan Sadique

Fig. LinkedBinaryTree class.

(Goodrich et al.: 8.3.2) Array-Based Representation of a Binary Tree:
An alternative representation of a binary tree T is based on a way of numbering the positions of T . For every
position p of T , let f (p) be the integer defined as follows.
• If p is the root of T , then f (p) = 0.
• If p is the left child of position q, then f (p) = 2 f (q) + 1.
• If p is the right child of position q, then f (p) = 2 f (q) + 2.

6
Data Structures and Algorithms – Lecture 6 Md. Farhan Sadique
4. Tree Traversal Algorithms (Goodrich et al.: 8.4, https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-
postorder/)

A traversal of a tree T is a systematic way of accessing, or “visiting,” all the positions of T .

4.1. Preorder Traversal of Trees (Goodrich et al.: 8.4)
In a preorder traversal of a tree T , the root of T is visited first and then the subtrees rooted at its children are
traversed recursively.

4.2. Postorder Traversal of Trees (Goodrich et al.: 8.4)

In some sense, this algorithm can be viewed as the opposite of the preorder traversal, because it recursively
traverses the subtrees rooted at the children of the root first, and then visits the root (hence, the name
“postorder”).

7
Data Structures and Algorithms – Lecture 6 Md. Farhan Sadique

4.3. Inorder Traversal of Trees (Goodrich et al.: 8.4.3)

For every position p, the inorder traversal visits p after all the positions in the left subtree of p and before all
the positions in the right subtree of p.

8
Data Structures and Algorithms – Lecture 6 Md. Farhan Sadique

9
Data Structures and Algorithms – Lecture 6 Md. Farhan Sadique
5. Binary Search Trees (Md. Rafiqul Islam and M. A. Mottalib: 7.2, https://www.geeksforgeeks.org/construct-bst-given-
level-order-traversal/ )

A binary search tree is a binary tree where all the node values of the left sub-tree are smaller than the node
value of the root of the tree, and all the node values of the right sub-tree are greater than the node value of
the root.

Construct a BST:
Construct a BST with the following list of values:
50, 15, 10, 13, 20, 22, 55, 60, 42, 57
Follow the steps below to solve the problem:
1) First, pick the first element of the array and make it root.
2) Pick the second element, if its value is smaller than the root node value, make it left child,
3) Else make it right child
4) Now recursively call step (2) and step (3) to make a BST from its level Order Traversal.

6. Heap (Md. Rafiqul Islam and M. A. Mottalib: 7.3)

It is a complete binary tree each of whose node’s value is greater (or smaller) than the node value of its
children. If the node value is greater than the node value of its children, then the heap is called max heap.
Otherwise, the heap is called min heap.

10
Data Structures and Algorithms – Lecture 6 Md. Farhan Sadique

Heap Creation:

11
Data Structures and Algorithms – Lecture 6 Md. Farhan Sadique

Bibliography
• Book: Data Structures and Algorithms in Java, Sixth Edition - Michael T. Goodrich, Roberto Tamassia and
Michael H. Goldwasser
• Book: Data Structures Fundamentals, Second Edition – Md. Rafiqul Islam and M. A. Mottalib
• Website: https://www.geeksforgeeks.org/complete-binary-tree/
• Website: https://www.geeksforgeeks.org/construct-bst-given-level-order-traversal/
• Website: https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/

12