MODULE 4: TREES

DEF INITION
A tree is a finite set of one or more nodes such that
• There is a specially designated node called root.
• The remaining nodes are partitioned into n >= 0 disjoint set T1 ,…,Tn , where each
of these sets is a tree. T1 ,…,Tn are called the subtrees of the root.

Every node in the tree is the root of some subtree

TERMINOLOGY
• Node: The item of information plus the branches to other nodes
• Degree: The number of subtrees of a node
• Degree of a tree: The maximum of the degree of the nodes in the tree.
• Terminal nodes (or leaf): nodes that have degree zero or node with no successor
• Nonterminal nodes: nodes that don’t belong to terminal nodes.
• Parent and Children: Suppose N is a node in T with left successor S1 and right
successor S2, then N is called the Parent (or father) of S1 and S2. Here, S1 is
called left child (or Son) and S2 is called right child (or Son) of N.
• Siblings: Children of the same parent are said to be siblings.
• Edge: A line drawn from node N of a T to a successor is called an edge
• Path: A sequence of consecutive edges from node N to a node M is called a path.
• Ancestors of a node: All the nodes along the path from the root to that node.
• The level of a node: defined by letting the root be at level zero. If a node is at level
l, then it children are at level l+1.
• Height (or depth): The maximum level of any node in the tree
Exampl e

A is the root node

B is the parent of E and F
C and D are the sibling of B E
and F are the children of B
K, L, F, G, M, I, J are external nodes, or leaves
A, B, C, D, E, H are internal nodes
The level of E is 3
The height (depth) of the tree is 4
The degree of node B is 2
The degree of the tree is 3
The ancestors of node M is A, D, H
The descendants of node D is H, I, J, M

Representation of Trees

There are several ways to represent a given tree such as:

Figure (A)

1. List Representation
2. Left Child- Right Sibling Representation
3. Representation as a Degree-Two tree
Li st Representati on:

The tree can be represented as a List. The tree of figure (A) could be written as the list.
(A (B (E (K, L), F), C (G), D (H (M), I, J) )
)

• The information in the root node comes first.

• The root node is followed by a list of the subtrees of that node.

Tree node is represented by a memory node that has fields for the data and pointers to the
tree node's children

Since the degree of each tree node may be different, so memory nodes with a varying
number of pointer fields are used.
For a tree of degree k, the node structure can be represented as below figure. Each child
field
is used to point to a subtree.

Left Chi l d-Ri ght Si bl i ng Representati on

The below figure show the node structure used in the left child-right sibling representation

To convert the tree of Figure (A) into this representation:

1. First note that every node has at most one leftmost child
2. At most one closest right sibling.
Ex:
• In Figure (A), the leftmost child of A is B, and the leftmost child of D is H.
• The closest right sibling of B is C, and the closest right sibling of H is I.
• Choose the nodes based on how the tree is drawn. The left child field of each node points
to its leftmost child (if any), and the right sibling field points to its closest right sibling
(if any).
Figure (D) shows the tree of Figure (A) redrawn using the left child-right sibling
representation.

Figure (D): Left child-right sibling representation of tree of figure

(A)

Representati on as a Degree -Two Tree

To obtain the degree-two tree representation of a tree, simply rotate the right-sibling pointers
in a left child-right sibling tree clockwise by 45 degrees. This gives us the degree-two
tree displayed in Figure (E).

Figure (E): degree-two representation

In the degree-two representation, a node has two children as the left and right children.
BINARY TREES
Definition: A binary tree T is defined as a finite set of nodes such that,
• T is empty or
• T consists of a root and two disjoint binary trees called the left subtree and the
right subtree.

Figure: Binary Tree

Diffe re nt kinds of Binary Tre e

1. Skewed Tree
A skewed tree is a tree, skewed to the left or skews to the
right. or
It is a tree consisting of only left subtree or only right subtree.
• A tree with only left subtrees is called Left Skewed Binary Tree.
• A tree with only right subtrees is called Right Skewed Binary Tree.

2. Compl ete Bi nary Tree

A binary tree T is said to complete if all its levels, except possibly the last level, have
the maximum number node 2 i, i ≥ 0 and if all the nodes at the last level appears as far
left as possible.

Figure (a): Skewed binary tree Figure (b): Complete binary tree
3. Ful l Bi nary Tree
A full binary tree of depth ‘k’ is a binary tree of depth k having 2 k – 1 nodes, k ≥ 1.

Figure: Full binary tree of level 4 with sequential node number

4. Extended Bi nary Trees or 2 -trees

An extended binary tree is a transformation of any binary tree into a complete binary
tree. This transformation consists of replacing every null subtree of the original tree
with “special nodes.” The nodes from the original tree are then internal nodes, while the
special nodes are external nodes.
For instance, consider the following binary tree.

The following tree is its extended binary tree. The circles represent internal nodes, and
square represent external nodes.
Every internal node in the extended tree has exactly two children, and every external
node is a leaf. The result is a complete binary tree.
P ROP ERTIES OF BINARY TREES

Lemma 1: [Maximum number of

nodes]:
(1) The maximum number of nodes on level i of a binary tree is 2 i-1 , i ≥
1.
(2) The maximum number of nodes in a binary tree of depth k is 2 k -1, k ≥
1.

Proof:
(1) The proof is by induction on i.
Induction Base: The root is the only node on level i = 1. Hence, the maximum number of
nodes on level i =1 is 2 i-1 = 20 = 1.
Induction Hypothesis: Let i be an arbitrary positive integer greater than 1. Assume that
the maximum number of nodes on level i -1is 2 i-2
Induction Step: The maximum number of nodes on level i -1 is 2 i-2 by the induction
hypothesis. Since each node in a binary tree has a maximum degree of 2, the maximum
number of nodes on level i is two times the maximum number of nodes on level i-1, or 2 i-1

(2) The maximum number of nodes in a binary tree of depth k

is k k
∑ (maximum number of nodes on level i) = ∑ 2i-1 = 2 k-1
i=0 i=0

Lemma 2: [Relation between number of leaf nodes and degree-2

nodes]:
For any nonempty binary tree, T, if n0 is the number of leaf nodes and n2 the number of
nodes of degree 2, then n0 = n2 + 1.

Proof: Let n1 be the number of nodes of degree one and n the total number of
nodes. Since all nodes in T are at most of degree two, we have
n = n0 + n1 + n2 (1)
Count the number of branches in a binary tree. If B is the number of branches,
then n =B + 1.
All branches stem from a node of degree one or two. Thus,
B =n 1 + 2n2 .
Hence, we
obtain n = B + 1= n 1 + 2n2 + 1 (2)

Subtracting Eq. (2) from Eq. (1) and rearranging terms, we get
n0 = n2 +1
Consider the figure:

Here, For Figure (b) n2 =4, n0 = n2 +1= 4+1=5

Therefore, the total number of leaf node=5

BINARY TREE REP RESENTATION

The storage representation of binary trees can be classified as
1. Array representation
2. Linked representation.

Array representation:
• A tree can be represented using an array, which is called sequential representation.
• The nodes are numbered from 1 to n, and one dimensional array can be used to
store the nodes.
• Position 0 of this array is left empty and the node numbered i is mapped to position i
of the array.

Below figure shows the array representation for both the trees of figure (a).
 • For complete binary tree the array representation is ideal, as no space is wasted.
• For the skewed tree less than half the array is utilized.

Linked representation:
The problems in array representation are:
• It is good for complete binary trees, but more memory is wasted for skewed and
many other binary trees.
• The insertion and deletion of nodes from the middle of a tree require the movement
of many nodes to reflect the change in level number of these nodes.

These problems can be easily overcome by linked representation

Each node has three fields,

• LeftChild - which contains the address of left subtree
• RightChild - which contains the address of right subtree.
• Data - which contains the actual information

C Code for node:

typedef struct node *treepointer;

typedef struct {
int data;
treepointer leftChild, rightChild;
}node;
 Figure: Node
representation

Linked representation of the binary

tree
BINARY TREE TRAVERSALS

Visiting each node in a tree exactly once is called tree traversal

The different methods of traversing a binary tree are:

1. Preorder
2. Inorder
3. Postorder
4. Iterative inorder Traversal
5. Level-Order traversal

1. Inorder: Inorder traversal calls for moving down the tree toward the left until you cannot
go further. Then visit the node, move one node to the right and continue. If no move can be
done, then go back one more node.

Let ptr is the pointer which contains the location of the node N currently being
scanned. L(N) denotes the leftchild of node N and R(N) is the right child of node N

Recursi on functi o n:
The inorder traversal of a binary tree can be recursively defined
as

• Traverse the left subtree in inorder.

• Visit the root.
• Traverse the right subtree in inorder.

void
inorder(treepointerptr)
{
if (ptr)
{
inorder (ptr→leftchild);
printf (“%d”,ptr→data);
inorder
} (ptr→rightchild);
}
2. Preorder: Preorder is the procedure of visiting a node, traverse left and continue. When
you cannot continue, move right and begin again or move back until you can move right and
resume.

Recursi on functi on:

The Preorder traversal of a binary tree can be recursively defined as
• Visit the root
• Traverse the left subtree in preorder.
• Traverse the right subtree in preorder

void preorder (treepointerptr)

{
if (ptr)
{
printf (“%d”,ptr→data)
preorder (ptr→leftchild);
preorder
} (ptr→rightchild);
}

3. Postorder: Postorder traversal calls for moving down the tree towards the left until you
can go no further. Then move to the right node and then visit the node and continue.
Recursion function:
The Postorder traversal of a binary tree can be recursively defined as
• Traverse the left subtree in postorder.
• Traverse the right subtree in postorder.
• Visit the root

void postorder(treepointerptr)
{
if (ptr)
{
postorder (ptr→leftchild);
postorder
(ptr→rightchild); printf
} (“%d”,ptr→data);
}
4. Iterati ve i norder Traversal :
Iterative inorder traversal explicitly make use of stack function.
The left nodes are pushed into stack until a null node is reached, the node is then removed
from the stack and displayed, and the node’s right child is stacked until a null node is
reached. The traversal then continues with the left child. The traversal is complete when the
stack is empty.

5. Level-Order traversal:
Visiting the nodes using the ordering suggested by the node numbering is called
level ordering traversing.
The nodes in a tree are numbered starting with the root on level 1 and so on.
Firstly visit the root, then the root’s left child, followed by the root’s right child. Thus
continuing in this manner, visiting the nodes at each new level from the leftmost node to
the rightmost node.

Level order traversal: 1 2 3 4 5

Initially in the code for level order add the root to the queue. The function operates
by deleting the node at the front of the queue, printing the nodes data field and adding the
nodes left and right children to the queue.
Function for level order traversal of a binary tree:

ADDITIONAL BINARY TREE OPERATIONS

1. Copying a Binary tree

This operations will perform a copying of one binary tree to another.

C function to copy a binary tree:

treepointer copy(treepointer original)

{ if(original)
{ MALLOC(temp,sizeof(*temp));
temp→leftchild=copy(original→leftchild);
temp→rightchild=copy(original→rightchild
); temp→data=original→data;
return temp;
}
return NULL;
}

2. Testi ng Equal i ty
This operation will determin the equivalance of two binary tree. Equivalance binary tree
have the same strucutre and the same information in the corresponding nodes.
C function for testing equality of a binary tree:
int equal(treepointer first,treepointer second)
{
return((!first && !second) || (first && second && (first→data==second→data)
&& equal(first→leftchild,second→leftchild) &&
equal(first→rightchild, second→rightchild))
}

This function will return TRUE if two trees are equivalent and FALSE if they are not.

3. The Sati sfi abi l i ty probl em

• Consider the formula that is constructed by set of variables: x1 , x2 , …, xn and
operators
(and), (or), ¬ (not).
• The variables can hold only of two possible values, true or false.
• The expression can form using these variables and operators is defined by
the following rules.
• A variable is an expression
• If x and y are expressions, then ¬x, xy, xy are expressions
• Parentheses can be used to alter the normal order of evaluation (¬ >  > )

Example: x1  (x2  ¬ x3 ) If x1 and x3 are false and x2 is true

= false  (true  ¬false)
= false  true
= true

The satisfiablity problem for formulas of the propositional calculus asks if there is
an assignment of values to the variable that causes the value of the expression to be
true.

Let’s assume the formula in a binary tree

(x1  ¬x2 )  (¬ x1  x3 )  ¬x3
The inorder traversal of this tree is
x1  ¬x2  ¬ x1  x3  ¬x3

The algorithm to determine satisfiablity is to let (x1 , x2 , x3 ) takes on all the possible
combination of true and false values to check the formula for each combination.

For n value of an expression, there are 2 n possible combinations of true and false
For example n=3, the eight combinations are (t,t,t), (t,t,f), (t,f,t), (t,f,f), (f,t,t), (f,t,f), (f,f,t),
(f,f,f).
The algorithm will take O(g 2 n ), where g is the time to substitute values for x1 , x2 ,… xn and
evaluate the expression.

Node structure:
For the purpose of evaluation algorithm, assume each node has four fields:

Define this node structure in C as:

Sati sfi abi l i ty functi on: The first version of Satisfiability algorithm