Resource Person:

Zafar Mehmood Khattak

Today Topics

 What are Trees?

 Types of Trees
 Binary Tree
 Full Binary Tree
 Extended Binary Tree
 Complete Binary Tree

 Binary Search Tree (BST)

 Constructing Binary Search Tree
 Representation of Binary Tree inside Computer
What are Trees?
 It is a non-linear data structure

 Each object of a tree starts with a root and extends into several
branches

 Each branch may extend into other branches until finally terminated
by a leaf

 Examples of the trees are:

 Lineage of a person that is referred to as the family tree

 Organizational chart of a company

 Game playing
 AI applications
What are Trees?
 It is an hierarchical collection of finite elements

 Each element is called a node

 A general tree is shown as:

What are Trees?
Trees have the following properties:

 Each tree has one node designated as the root of the tree

 A unique path exists from the root node to all other nodes in the tree

 Each node, other that the root, has a unique predecessor, it is also
called the parent

 Each node may have no, one or several successor nodes, it is also
called the child
General characteristics of trees
 Node
 Degree
 Children
 Parent
 Siblings
 Ancestors
 Leaves
 Path from node n1 to nk
 a sequence of nodes n1,n2,...,nk such that ni is the parent of ni+1 for 1<= i < k
 Path length
 Level
 Height of a node
 Height of a tree
 Depth of a node
 Depth of a tree
 Along with arrays and lists, trees are the most frequently encountered data
structure in computer algorithms
Basic terms of Trees

 Root Node
 The unique node in the tree that has no parent node

 Parent Node
 The node, which generates links for other nodes

 Child Node
 The node that is directly connected to a parent node

 Subtrees
 The child node of the root node that has its own child nodes
 Basic terms of Trees
 Terminal or leaf Node
 The node having no successor or child

 Siblings
 The nodes having a common parents

 Depth of Node
 Each node has a unique path connecting it to the root. The depth of a node is
the total number of nodes between the node and root

 Height of Tree
 The maximum depth among all of the nodes of a tree
Basic terms of Trees
 Empty Tree
 A tree that has no node

 Degree of Node
 The number of children of a node

 Full Tree
 A tree, which all its internal nodes have the same degree and all the
leaves are at the same level

 Singleton Tree
 The tree whose root is its only node
Basic terms of Trees

 Height of a node u is the height of the subtree rooted at u

 Level of a node is defined by letting root be at level 0. If
node is at level i, then its children are at level i +1
 Degenerate tree – only one child
 Balanced tree – mostly two children
 Complete tree– always two children
Binary Tree

 It is a hierarchical collection of a finite number of nodes in

which each node can have a maximum of two children

 One child is on the left side

 One child is on the right side

 It may be empty or non-empty but a general tree cannot

be empty
 Binary Tree

A non-empty binary tree may have the three parts:

 Root Node
 The node that has no parent

 Left Child Node

 The node that lies on the left side of the root

 Right Child Node

 The node that lies on the right side of the root
 Binary Tree ADT: Properties

 Full Binary Tree:

 All the internal nodes, non-leaf nodes, have two children.
 All the leaves are at the same depth k.
 The number of internal nodes in depth k tree is 2k - 1, where k >= 0
 The number of leaves in a depth k tree is 2k
 The total number of nodes in a depth k tree is 2k+1 - 1
 The height of the tree with n nodes is log2(n + 1)-1

Internal node: the node having two

child
External node: the node having no
 Binary Tree ADT: Properties

 Proper Binary Tree

 All the internal nodes have two children.
 The leaves can be located at different depths.
 The number of internal nodes in a depth k tree is at least k and at
most 2k - 1, where k >= 0
 The number of leaves in a depth k tree is at least k + 1 and most 2k
 The total number of nodes in a depth k tree is at least 2k + 1 and at
most 2k+1 – 1
 The height of the tree with n nodes is at least log2(n + 1)-1 and at
most (n-1)/2
Full Binary Tree
 .
Extended Binary Tree
 A binary tree in which each node has either no child or two children
 It is also called 2-Tree
 The node that has two children is called internal node
 The node that has no child is called external node
How to find height of binary
tree:
 Suppose a point p to the root node is given,
 If binary tree is empty then height is 0, else
 Find the height of the left sub tree and then find
the height of right sub tree and then add 1 to find
the find height of binary tree.
 If(p==NULL)
 Height(p)=0;
 Return 0;
 Else
 return 1+(max(height(p->llink), height (p->rlink)
Constructing Binary Search
Tree
 Suppose the BST have the following values to be const.

 16, 19, 15, 9, 8, 66, 12, 61

 The following rule are followed to construct the BST.
 1. place the first value as root.
 2. Compare the second value with the root value, and place to
the left of the root if it is less than root. Other wise place to
right.
 3. repeat step 2 for all values starting from root.
 But keep in mind that duplication of values in BST is not
allowed.
 Constructing BST
 .

16

19
15

66
9

8 12 61
Operation on binary tree

 Insertion
 Deletion
 Searching
 Traversing

 Write algorithm and code for deletion and

traversing by yourself,
 Insertion.
 Adding a value to BST can be divided into two stages:
 search for a place to put a new element;
 insert the new element to this place.
 At this stage algorithm should follow binary search tree
property. If a new value is less, than the current node's value, go
to the left subtree, else go to the right subtree. Following this
simple rule, the algorithm reaches a node, which has no left or
right subtree. By the moment a place for insertion is found, we
can say for sure, that a new value has no duplicate in the tree.
Initially, a new node has no children, so it is a leaf.
 Insertion algorithm.

1. check, whether value in current node and a new value are equal. If
so,
1.1. duplicate is found.
1.2. And exit, Otherwise,
2. if a new value is less, than the node's value:
2.1. if a current node has no left child,
2.2 place for insertion has been found;
2.3. otherwise, handle the left child with the same algorithm.
3. if a new value is greater, than the node's value:
3.1. if a current node has no right child,
3.2. place for insertion has been found;
3.3. otherwise, handle the right child with the same algorithm.
 Insertion code.

 bool BinarySearchTree::add(int value) {

       if (root == NULL) {
             root = new BSTNode(value);
             return true;
       } else
             return root->add(value);
 }
  
 bool BSTNode::add(int value) {
       if (value == this->value)
             return false;
       else if (value < this->value) {
             if (left == NULL) {
                   left = new BSTNode(value);
                   return true;
             } else
                   return left->add(value);
       } else if (value > this->value) {
             if (right == NULL) {
                   right = new BSTNode(value);
                   return true;
             } else
                   return right->add(value);
       }
       return false; }
Searching

 searching for a value in a BST is very similar to

add operation. Search algorithm traverses
the tree "in-depth", choosing appropriate
way to go, following binary search tree
property and compares value of each visited
node with the one, we are looking for.
Algorithm stops in two cases:
 a node with necessary value is found;
 algorithm has no way to go.
Searching
1. check, whether value in current node and searched
value are equal. If so,
1. value is found.
2. Exit , Otherwise,
2. if searched value is less, than the node's value:
 if current node has no left child, searched value doesn't
exist in the BST;
 otherwise, handle the left child with the same algorithm.
3. if a new value is greater, than the node's value:
 if current node has no right child, searched value doesn't
exist in the BST;
 otherwise, handle the right child with the same
algorithm.
Searching
 bool BinarySearchTree::search(int value)
 {
       if (root == NULL)
             return false;
       else
             return root->search(value);
 }
  
bool BSTNode::search(int value) {
       if (value == this->value)
             return true;
       else if (value < this->value) {
             if (left == NULL)
                   return false;
             else
                   return left->search(value);
       } else if (value > this->value) {
             if (right == NULL)
                   return false;
             else
                   return right->search(value);
       }
       return false;
 }
Tree Traversal

 In a traversal, each and every node is visited once

 A full traversal produces a linear order for the
nodes
 Traversal Methods:
 Inorder (Left Child, Node, Right Child)
 Preorder (Node, Left Child, Right Child)
 Postorder (Left Child, Right Child, Node)
 Level Order Traversal
 Inorder Traversal (LNR: left, node, right)

 algorithm inorder(Treeptr T);

 (T is a pointer to a node in a binary tree. For full tree
traversal, pass inorder the pointer to the top of the tree )
 begin
 if T != NULL
 then
 inorder(T->Lchild);
 write(T->element); output: FDBGEACH
 inorder(T->Rchild);
 endif
 inorder traversal, left, node, right.

 .

infix expression
a+b*c+d*e+f*g
Preorder Traversal (NLR: node, left,
right)
algorithm preorder(Treeptr T);
(T is a pointer to a node in a binary tree. For full tree
traversal, pass preorder the pointer to the top of the
tree)
begin
if T != NULL
then
write(T->data);
preorder(T->Lchild);
preorder(T->Rchild); Preorder
endif

Output: ABDFEGCH
PostOrder Traversal (LRN: left, right,
node)
algorithm postorder(Treeptr T);
(T is a pointer to a node in a binary tree. For full
tree traversal, pass postorder the pointer to the top
of the tree)
begin
if T != NULL
then
postorder(T->Lchild);
postorder(T->Rchild);
write(T->data);
endif
Output: FDGEBHCA
 Postorder traversal, left, right, node.

 .

postfix expression
abc*+de*f+g*+
Traversing code

 Void intorder(int *p)

{
if( p!= NULL);
Cout<<(p->llink);
Inordeer(p->rlink);
}
}
And same for the post and pre order.
Level-Order Traversal
 First visit the root, then the root's left child, followed by the root's
right child, continue in this manner, visiting nodes at each new level
from leftmost node to rightmost node
 May need a queue structure to realize this traversal

algorithm LevelOrder(Treeptr T);

begin
front = 0; rear = 0 {initialize queue}
enqueue(T);
while (! queue_empty() ) do
dequeue(T);
write(T->data);
if T->Lchild not null then
enqueue(T->Lchild);
if T->Rchild not null then
enqueue(T->Rchild);
endwhile
end algorithm
Output: ABCDEHFG
Application: Expression Trees

 Algorithm to construct an expression tree given a

postfix expression (e.g. a b + c d e + * *)
 Read one symbol at a time
 If symbol is an operand, create a one-node tree and
push pointer to it onto stack
 If symbol is an operator, pop pointers to two trees, T1
and T2, from the stack and form a new tree whose
root is the operator and whose left and right children
point to T2 and T1, respectively (T2 oper T1)
 Push the pointer to the new tree onto the stack
 Example
Construct an expression tree given a postfix expression (e.g. a b + c d e + * *)
Application: Expression Trees

 E= ( a + b * c ) + (( d * e + f) * )

 Leaves are operands (constants or variables)

 The other nodes (internal nodes) contain operators

 Will not be a binary tree if some operators are not binary

Example: Expression Trees
Class assignments, make a list

 Examples
5

10 10
2 45

5 30 5 45
30
2 25 45 2 25 30
10

25

Binary search Non-binary search

trees tree
Representation of BT in computer
 Two techniques are there to use.
 Linked storage technique.
 Most commonly used method for storing tree.
 This technique is almost similar to two way linked list
 Each node of the binary tree is represented by a three
fields.
 Each node contains two pointer fields, one for left child
and one for right child, and the third one is used to store
the value.
 If a root node contains no child, then the left and right
pointer fields contains the NULL values.
 The pointer fields values for both left and right children
of leaves nodes are always NULL.
 Example of BT in memory

 The following example explains a node structure of the

tree:
struct node
{
int data;
node *left;
node *right;
};

“data” is of int type and is used to store integer values in

the node.

 “left” as a pointer to store memory address for left child

of the tree.
 “right” as a pointer to store memory address for right
child of the tree.
Representation of BT in
computer
 Sequential storage technique.
 Linear array is used to represent the tree inside the
computer.
 Best for static tree, structure cant not be changed, e.g.
binary tree, with the following rules.
 1. Root R is stored in first element of the array.
 2. The left child of the node k is stored in element
2 * K of the array.
 3. The right child of the node K is stored in element
2 * K+1 of the array.
 Where k represents the number of nodes of the tree.
Class assignments.

 42, 11, 87, 9 22, 99

 These are the values of binary tress,
 First construct BST form the given values
 Then represent it in memory.
 E= (a – b) / ( c * d) * e)
 Construct a binary tree from the given
expression.