Trees

Compiled By :: Devesh Lowe

Introduction to Tree
 Fundamental data storage structures used in programming.
 Non-linear
 Mainly used to represent data containing a hierarchical
relationship between elements e.g. records, family trees, and
table of contents
 Combines advantages of an ordered array and a linked list.
 Searching as fast as in ordered array.
 Insertion and deletion as fast as in linked list.
 Binary Trees
 Every node in a binary tree can have at most
two children.
 The two children of each node are called the
left child and right child corresponding to
their positions.
 A node can have only a left child or only a right
child or it can have no children at all.
 A binary tree T is defined as a finite set of
elements, called nodes such that:
 T is empty (callled null tree or empty tree)
 T contains a distinguished node R, callled
root of T, and the remaining nodes of T form
an ordered pair of disjoint binary trees T1
and T2
 Parts of a binary tree

 A binary tree is composed of zero or more nodes

 Each node contains:
 A value (some sort of data item)
 A reference or pointer to a left child (may be null), and
 A reference or pointer to a right child (may be null)
 A binary tree may be empty (contain no nodes)
 If not empty, a binary tree has a root node
 Every node in the binary tree is reachable from the root node by a
unique path
 A node with no left child and no right child is called a leaf
 In some binary trees, only the leaves contain a value
4
 Picture of a binary tree
The root is
drawn at the top a

b c

d e f

g h i j k

5
l
 Left ≠ Right
 The following two binary trees are different:

A A

B B

 In the first binary tree, node A has a left child but no right child; in the
second, node A has a right child but no left child
 Put another way: Left and right are not relative terms

6
 More terminology
 Node A is the parent of node B if node B is a child of A
 Node A is an ancestor of node B if A is a parent of B, or if
some child of A is an ancestor of B
 In less formal terms, A is an ancestor of B if B is a child of A, or
a child of a child of A, or a child of a child of a child of A, etc.
 Node B is a descendant of A if A is an ancestor of B
 Nodes A and B are siblings if they have the same parent
 Binary Trees T and T` are said to be similar if they have
the sa,e structure or, in other words they have same
shape.
 The trees are said to be copies if they are similar and if
7 they have the same content at corresponding nodes.
 Size and depth
 The size of a binary tree is the
a number of nodes in it
 This tree has size 12
b c  The depth of a node is its distance
from the root
d e f  a is at depth zero
 e is at depth 2
g h i j k  The depth of a binary tree is the
depth of its deepest node
l  This tree has depth 4

8
 Complete Tree
 A tree T is said to be complete if all its
levels except possibly the last , have the
maximum number if possible nodes, and all
nodes at last level appear as far left as
possible.
 A complete tree ensures:
 optimum utilization of memory space
 Keeps depth of tree in check
 Keeps tree balance
 Reduces the average search time.
 A complete tree with all leaf nodes are at
the same level becomes a Full Tree

9
 Extended binary tree or 2-Tree
 A binary tree T is said to be a 2-tree or an extended binary tree if
each node N has either 0 or 2 children.
 In such a case, the nodes with 2 children are called internal nodes,
and the nodes with 0 children are called external nodes
 Sometimes the nodes are distinguished in diagrams by using circles
for internal nodes and squares for external nodes.
 The term extended comes form following operation:
 Sometimes a binary tree is converted to a 2-tree by replacing each empty
subtree by a new node.
 Nodes of the original tree become internal nodes and added nodes or
extended nodes become external nodes.
 A 2-tree is ideal for implementations like algebric expressions.

10
 Balance
a a
b c b
c e
d e f g
d f
h i j
g h
A balanced binary tree
i j
An unbalanced binary tree

 A binary tree is balanced if every level above the lowest is “full” (contains
2n nodes)
 In most applications, a reasonably balanced binary tree is desirable

11
 Representation of Binary trees in memory

 Tree can be represented in memory in two ways:

 The first and the usual way is called link representation of T
and is analogous to the way linked list are represented in
memory.
 The second method which uses a single dimension array,
called the sequential representation of T.
 In both the cases any node N can have direct access to its
successor nodes.

12
 Linked representation of Tree
 Tree T will be maintained in memory by means of linked
representation which uses structure objects containing two
pointers of tree type, apart from storing data, to hold address
of left and right successor.
 Formation will be :
Struct Tree
{
int data;
Tree *left, *right;
}root;

13
 Sequential representation of Tree
 In this method we can store pointers/references of tree
nodes using an array in memory called as sequential
representation such that:
 The root of T is stored in TREE[k]
 Left child of root is stored in Tree[2*k]
 Right child of root is stored in Tree[2*k+1]
 Same rule is followed on every sub tree
 This formation is ideally suited for complete tree or full trees
to avoid any unnecessary wastage of memory space.

14
 binary search trees
 A binary tree is sorted if every node in the tree is larger than
(or equal to) its left descendants, and smaller than (or equal
to) its right descendants
 Equal nodes can go either on the left or the right (but it has
to be consistent)

10

8 15

4 12 20

15 17
 Binary search in a sorted array
 Look at array location (lo + hi)/2

Searching for 5:
(0+6)/2 = 3
Using a binary
hi = 2;
(0 + 2)/2 = 1 lo = 2; search tree
(2+2)/2=2
7

3 13
0 1 2 3 4 5 6
2 3 5 7 11 13 17 2 5 11 17
16
 Tree traversals
 A binary tree is defined recursively: it consists of a root, a left
subtree, and a right subtree
 To traverse (or walk) the binary tree is to visit each node in the
binary tree exactly once
 Tree traversals are naturally recursive
 Since a binary tree has three “parts,” there are three main ways to
traverse the binary tree:
 Pre-order (root, left, right)
 In-order (left, root, right)
 Post-order (left, right, root)

17
 class BinaryTree
 class BinaryTree<V> {
V value;
BinaryTree<V> leftChild;
BinaryTree<V> rightChild;

// Assorted methods…
}
 A constructor for a binary tree should have three parameters,
corresponding to the three fields
 An “empty” binary tree is just a value of null

18
 Preorder traversal (recursive)
 In preorder, the root is visited first, followed by left child and right
child.
 Here’s a preorder traversal to print out all the elements in the
binary tree:

void preorderPrint(BinaryTree bt) {

if (bt == null) return;
printf(“%d”,bt->data);
preorderPrint(bt->leftChild);
preorderPrint(bt->rightChild);
}

19
 Pre-order (non-recursive)
Initially push NULL onto STACK and then set PTR:=ROOT.
Then repeat the following steps while PTR!=NULL
1. Proceed down the left most path rooted at PTR, processing
each node N on the path and pushing each right child
R(N), if any, onto STACK. The traversing ends after a node
N with no left child L(N) is processed. PTR is updated like
PTR:=PTR(left)
2. [Backtracking] Pop and assign to PTR the top element on
STACK. If PTR!=NULL, then return to previous step.
Otherwise exit.

20
 Inorder traversal (recursive)
 In inorder, the root is visited in the middle. Every tree’s left child is
visited, then root, then right child
 Here’s an inorder traversal to print out all the elements in the
binary tree:

void inorderPrint(BinaryTree bt) {

if (bt == null) return;
inorderPrint(bt->leftChild);
printf(“%d”,bt->value);
inorderPrint(bt->rightChild);
}

21
 Inorder traversal (non recursive)
Initially push NULL onto STACK and then set PTR:=ROOT.
Then repeat the following steps while PTR!=NULL
1. Proceed down the left most path rooted at PTR, pushing
each node N onto STACK and stopping when a node with
no left child is pushed on stack.
2. [Backtracking] Pop and process the nodes on STACK. If
NULL is popped then exit. If node N with a right child
R(N) is processed, set PTR=R(N) then return to previous
step.

22
 Postorder traversal ( recursive )
 In postorder, the root is visited last. Sequence startw with visiting left
node, then root node then right node.
 Here’s a postorder traversal to print out all the elements in the
binary tree:

void postorderPrint(BinaryTree bt) {

if (bt == null) return;
postorderPrint(bt->leftChild);
postorderPrint(bt->rightChild);
printf(“%d”,bt->value);
}

23
 Postorder traversal (non recursive)
Initially push NULL onto STACK and then set PTR:=ROOT.
Then repeat the following steps while PTR!=NULL
1. Proceed down the left most path rooted at PTR, At each
node N of the path, push N onto STACK, and if N has a
right child R(N), push –R(N) pushed on stack.
2. [Backtracking] Pop and process positive nodes on STACK.
If NULL is popped then exit. If a negative node is popped,
i.e. if PTR=-N for some node N, set PTR=N and return to
step 1

24
 Tree traversals using “flags”
 The order in which the nodes are visited during a tree traversal
can be easily determined by imagining there is a “flag” attached to
each node, as follows:

preorder inorder postorder

 To traverse the tree, collect the flags:

A A A

B C B C B C

D E F G D E F G D E F G

25
ABDECFG DBEAFCG DEBFGCA
 Other traversals
 The other traversals are the reverse of these three standard ones
 That is, the right subtree is traversed before the left subtree is
traversed
 Reverse preorder: root, right subtree, left subtree
 Reverse inorder: right subtree, root, left subtree
 Reverse postorder: right subtree, left subtree, root

26
Finding a Node
 To find a node given its key value, start from the root.
 If the key value is same as the node, then node is found.
 If key is greater than node, search the right subtree, else
search the left subtree.
 Continue till the node is found or the entire tree is traversed.
 Time required to find a node depends on how many levels
down it is situated, i.e. O(log N).
 Search a value
t=root;
Flag=0;
while(t!=NULL)
{ if( t->data == value)
{ flag=1; break; }
else if( value < t->data)
t=t->left;
else
t=t->right;
}
if(flag==1)
printf("\nElement found");
else
printf("\nElement not found");

28
Inserting a Node
 To insert a node we must first find the place to insert it.
 Follow the path from the root to the appropriate node, which
will be the parent of the new node.
 When this parent is found, the new node is connected as its
left or right child, depending on whether the new node’s key
is less or greater than that of the parent.
 Inserting a new node (recursive)
Void insert(Tree *root, Tree *newnode)
{
if( newnode->data < root->data)
{
if(root->left==NULL)
root->left=newnode;
else
insert(root->left,newnode);
}
else
{
if(root->right==NULL)
root->right=newnode;
else
Insert( root->right, newnode);
}
}

30
Finding Maximum and Minimum Values
 For the minimum,
 go to the left child of the root and keep going to the left child
until you come to a leaf node. This node is the minimum.
 For the maximum,
 go to the right child of the root and keep going to the right
child until you come to a leaf node. This node is the maximum.
Deleting a Node
 Start by finding the node you want to delete.
 Then there are three cases to consider:
1. The node to be deleted is a leaf
2. The node to be deleted has one child
3. The node to be deleted has two children
Deletion cases: Leaf Node
 To delete a leaf node, simply change the appropriate child
field in the node’s parent to point to null, instead of to the
node.
 The node still exists, but is no longer a part of the tree.
 So we can comfortably delete the node.
Deletion: One Child
 The node to be deleted in this case has only two connections:
to its parent and to its only child.
 Connect the child of the node to the node’s parent, thus
cutting off the connection between the node and its child,
and between the node and its parent.
Deletion: Two Children
Deletion: Two Children
 To delete a node with two children, replace the node with its
inorder successor.
 For each node, the node with the next-highest key (to the deleted
node) in the subtree is called its inorder successor.
 To find the successor,
 start with the original (deleted) node’s right child.
 Then go to this node’s left child and then to its left child and so on, following
down the path of left children.
 The last left child in this path is the successor of the original node.
Find successor
Delete a node with subtree (case 1)
Delete a node with subtree (case 2)
Delete a node with subtree (case 3)
Expression Tree

43
 A Binary Expression Tree is . . .

A special kind of binary tree in which:

1. Each leaf node contains a single operand

2. Each nonleaf node contains a single binary

operator

3. The left and right subtrees of an operator node

represent subexpressions that must be evaluated
before applying the operator at the root of the
subtree.
44
A Four-Level Binary Expression

‘*’

‘-’ ‘/’

‘8’ ‘5’ ‘+’ ‘3’

‘4’ ‘2’

45
 Levels Indicate Precedence

The levels of the nodes in the tree indicate their

relative precedence of evaluation (we do not need
parentheses to indicate precedence).

Operations at higher levels of the tree are

evaluated later than those below them.

The operation at the root is always the last

operation performed.

46
A Binary Expression Tree

‘*’

‘+’ ‘3’

‘4’ ‘2’

What value does it have?

( 4 + 2 ) * 3 = 18
47
 Easy to generate the infix, prefix, postfix expressions

‘*’

‘-’ ‘/’

‘8’ ‘5’ ‘+’ ‘3’

‘4’ ‘2’

Infix: ((8-5)*((4+2)/3))
Prefix: *-85 /+423
Postfix: 85- 42+3/*
48
 Inorder Traversal: (A + H) / (M - Y)

Print second
tree

‘/’

‘+’ ‘-’

‘A’ ‘H ‘Y
’ ‘M’ ’

Print left subtree first Print right subtree last

49
 Preorder Traversal: / + A H - M Y

Print first
tree

‘/’

‘+’ ‘-’

‘A’ ‘H ‘Y
’ ‘M’ ’

Print left subtree second Print right subtree last

50
 Postorder Traversal: A H + M Y - /

Print last
tree

‘/’

‘+’ ‘-’

‘A’ ‘H ‘Y
’ ‘M’ ’

Print left subtree first Print right subtree second

51