Introduction to Trees

Chapter 4 of textbook 1
Why we need to learn Tree structure
• Efficient Data Organization
– Examples: File directories, organizational charts
• Representation of Hierarchical Data
– Examples: family trees, decision trees
• Fast Search and Retrieval
– BST, AVL Tree
• Foundational Knowledge for Advanced Concepts
– Graph, priority queues.
 Formal Definition
A tree is a collection of nodes.
There is a starting node known as root node.
Every node other than the root has a parent node.
Nodes may have any number of children.
Nodes with no children are known as leaves

A has 3 children, B, C, D A Some Terminologies:

Father (or parent) =
A is parent of B
ancestor
E is leaf B C D Child = descendant
brother =sibling
E F G (same parent)
Path to a node p is a sequence of nodes root, n1, n2, …..p such
that n1is a child of root, n2is a child of n1……
Path to E is ? A,B, E

How many paths are there to one node? Just one!

Depth of a node is the length of the unique path

from the root to the node (not counting the node).
Root is at depth 0
Depth of E is ? 2
Leaves are nodes without any children.
D and E are leaf nodes.

Height of a non-leaf node is the length of the LONGEST path from

the node to a leaf (not counting the leaf).
Height of a leaf is 0
Height of A is ? 2
 Application
Organization of a file system. Root

Root directory
EE220 CSE260 TCOM500
EE220, CSE260, TCOM 500
EE220: Lecture Notes, HW Lec HW

Every node has one or more elements:

Directory example: element of a node is the
name of the corresponding directory
 Implementation

Using pointers
A node has a pointer to all its children
Since a node may have many children, the child pointers
have a linked list. A

A has a pointer to B, C, D each.

B C D
B has pointers to E and its other child.
E does not have any pointers. E F G
Example
 Addition of a child:
Create the new child node
Add a pointer to this child in the link list of
its parent.

Want to add new child A

H to B

B C D

E F

H
Deletion of a child B:
Children of B are first made children of the A
parent of B
Node B is deleted. B C D

E F

B C D
E
F
 A

C D
E
F
Deletion of the root:
One of the children becomes the new root:
Other children of old root become the children of the new root

B C D

E F G

C becomes new root

B and D are children of C in addition to its
original child
 C

B D
G

E F
 Tree Traversal (Tree Search)
Many algorithms involve walking through a tree,
and performing some computation at each node

Walking through a tree is called a traversal

Depth-First Search (DFS):

– Pre-order
– Post-order
– In-order (applied for Binary Tree)

Breadth-First Search (BFS) or Level-order Search

 DFS: Pre-order
A

B C D

E F G

Pre-order:
First visit a node, then with its children (visit means
performing some computation at this node)
A→B→E→F→C→G→D
 DFS: Post-order
A

B C D

E F G

Post-order:
First visit its children, then return to the node. (visit means
performing some computation at this node)
E→F→B→G→C→D→A
 BFS
A

B C D

E F G

BFS:
Visit all nodes at the current level before moving to the next.

A → B→C→D→E→F-G
 Binary Trees

A node can have at most 2

children, leftchild and rightchild

What is the largest

depth of a binary tree
of N nodes? N -1
 In-order Traversal

First visit the left subtree

Then visit the node
Then visit right subtree

4→2→5→1→6→3→7
 Quiz
Please give the order of nodes we visit:
DFS Pre-order
DFS Post-order
DFS In-order
BFS (Level-order)
 Implementation of a binary tree
node
struct BinaryTreeNode
{
ElementType Element;
BinaryTreeNode * left;
BinaryTreeNode * right;
};

typedef struct BinaryTreeNode* PtrToNode;

 Implementation of Pre-order
Recursive function

Performing some computations here is to print the data

Time complexity?
 Implementation of Pre-order (2):
Non-recursive function
Stack treeStack;
currNode = root;
While(!isEmpty(treeStack) || currNode != NULL)
{
if(currNode !=NULL)
{
printf(currNode→data);
push(treeStack, currNode);
currNode = currNode→left;
}
else {
prevNode = pop(Stack);
currNode = prevNode→right; Stack is used here
}
}
 Implementation of Post-order
Recursive function Non-recursive function

Homework

Time complexity?
 Implementation of In-order
Recursive function Non-recursive function

Homework
Implementation of BFS

Queue is used here

 Binary Search Tree (BST)
Time complexity of searching in a binary tree is O(n).
We introduce a binary search tree which is useful for searching
with a time complexity of O(log N) in average case.

What is a binary search tree?

All elements in the left subtree of a node are smaller
than the element of the node, and all elements in the
right subtree of a node are larger.
We will assume that in any binary tree, we are not
storing duplicate values unless otherwise stated.
BST
 5

Not binary Search Tree

3 1

1 4 10

Binary Search Tree

3 8

1 4 10
 Another Examples
5 8

4 8 5 11

1 7 11 2 7 6 10 18

3 4 15 20

BINARY SEARCH TREE 21

NOT A
BINARY SEARCH TREE
 All these binary search trees
store the same data
All these binary search trees store the
same data
 Finding X in the Tree
Start from the root.
Each time we encounter a node, check if its value
equals X. If yes, stop.
If X is less, go to the left subtree.
If it is more, go to the right subtree.
Conclude that X is not in the list if we reach a leaf
node and the element in the node does not equal X.
To determine membership, traverse the tree based on the linear
relationship:
– If a node containing the value is found,e.g., 81, return 1
(Found)

– If an empty node is reached,e.g., 36, the object is not in the

tree.
 Recursive version of search
Search(root, X)
{
node = root;
If (node = NULL) return NOT FOUND;
Else If (node→element == X) return FOUND;
Else If (X < node→element) Search(node→leftchild, X);
Else If (X > node→element) Search(node→rightchild, X);
}
Complexity: O(d), d is the depth,
Average case d= log N
 5

Search for 10
3 8
Sequence Traveled:
1 4 10 5, 8, 10
Found!

Search for 3.5

Sequence Traveled:
5, 3, 4
Not found!
Quiz: Non-recursive version of
search
 Find Min and Find Max

Find Min: start at the root and go left as long as there is a left child. The
stopping leaf is the smallest element.
Find Max: start at the root and go right as long as there is a right child.
The stopping leaf is the greatest element.

Complexity: O(d)
 5

3 8

1 4 10

Travel 5, 3, 1
Return 1;

Travel 5, 8, 10
Return 10;
 Quiz: implementation
Provide the recursive version and non-recursive
version of Find Min and Find Max

Find_Min(root): Find_Min(root):
T = root; T = root;
If(T != NULL) If(T != NULL)
while(T→left != NULL) if (T→ left != NULL)
T=T→left; Find_Min(T-left);
return(T); return T;
 Insertion
An insertion will be performed at a leaf
node:
– Any empty node is a possible location for
an insertion
 Insertion
For example, this node may hold 48, 49,
or 50
 Insertion
An insertion at this location must be 35,
36, 37, or 38
 Insertion
This empty node may hold values from 71
to 74
 Insertion Algorithm

Like find, we will step through the tree

o If we find the object already in the tree, we will return
o The object is already in the binary search tree (no
duplicates)
o Otherwise, we will arrive at an empty node
o The object will be inserted into that location
 Insertion: example 1
In inserting the value 52, we traverse the
tree until we reach an empty node
– The left sub-tree of 54 is an empty node
 Insertion: example 1
A new leaf node is created and assigned
to the member variableleft of 54
 Insertion: Example 2
In inserting 40, we determine the right
sub-tree of 39 is an empty node
 Insertion: example 2
A new leaf node storing 40 is created and
assigned to the member pointerright
of 39
Complexity: O(d)
 Quiz: Insertion
Blackboard example:
– In the given order, insert these objects into an initially empty
binary search tree:
31 45 36 14 52 42 6 21 73 47 26 37 33 8
– What values could be placed:
• To the left of 21?
• To the right of 26?
• To the left of 47?
– How would we determine if 40 is in this binary search tree?
– Which values could be inserted to increase the height of the
tree?
 Erase (Deletion)
A node being erased is not always going to be a leaf
node
There are three possible scenarios:
– The node is a leaf node,
– It has exactly one child, or
– It has two children (it is a full node)
 Erase

A leaf node simply must be removed and the

appropriate member variable of the parent is
set toNULL
– Consider removing 75
 Erase
The node is deleted and left pointer of
81 is set to NULL
 Erase
Erasing the node containing 40 is similar
 Erase
The node is deleted and right pointer
of 39 is set to NULL
 Erase
If a node has only one child, we can simply
promote the sub-tree associated with the
child
– Consider removing 8 which has one left
child
 Erase
The node 8 is deleted and the left pointer of
11 is updated to point to 3.
 Erase

There is no difference in promoting a single

node or a sub-tree
– To remove 39, it has a single child 11
 Erase
The node containing 39 is deleted and
left_node of 42 is updated to point to 11
– Notice that order is still maintained
 Erase
Consider erasing the node containing 99
 Erase
The node is deleted and the left sub-tree
is promoted:
– The member variable right pointer of
70 is set to point to 92.
– Again, the order of the tree is maintained.
 Erase
Finally, we will consider the problem of erasing a full
node,e.g., 42
We will perform two operations:
– Replace 42 with the minimum object in the right
sub-tree and Erase that object from the right sub-
tree OR
– Replace 42 with the maximum object in the left sub-
tree and Erase that object from the left sub- tree
 Erase
In this case, we replace 42 with 47
– We temporarily have two copies of 47 in
the tree
 Erase
We now recursively erase 47 from the
right sub-tree
– We note that 47 is a leaf node in the right
sub-tree
 Erase

Leaf nodes are simply removed andleft pointerof 51

is set toNULL
– Notice that the tree is still sorted:
47 was the least object in the right sub-tree
 Erase

Suppose we want to erase the root 47 again:

– We must copy the minimum of the right
sub-tree
– We could promote the maximum object in
the left sub-tree and achieve similar results
 Erase
We copy 51 from the right sub-tree
 Erase
We must proceed by delete 51 from the
right sub-tree
 Erase
In this case, the node storing 51 has just
a single child
 Erase
We delete the node containing 51 and
assign the member variableleft
pointerof 70 to point to 59.
 Erase
Note that after seven removals, the
remaining tree is still correctly sorted
 Erase
In the two examples of removing a full node, we
promoted:
– A node with no children
– A node with right child
Is it possible, in removing a full node, to promote a child
with two children?
 Pseudo Code
Delete(node): {
If a node is childless, then
{
node→parent→ptr_to_node = NULL
free(node);
}

If a node has one child

{
node→parent→child = node→child;
free(node);
}
 If a node has 2 children,
{
minnode = findmin(rightsubtree)→key;
node→key = minnode→key;
delete(minnode);
}
}

Complexity? O(d)
 Quiz: Erase
Blackboard example:
– In the binary search tree generated
previously:
• Erase47
• Erase21
• Erase45
• Erase31
• Erase36
 Next week
• Online Assignment 2
– Duration :45 minutes
– Content: Stack, Queue, Tree
• AVL Tree