Data Structure and Algorithms
CSC211
Lecture # 26
Representation of Trees
List Representation
– ( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) )
– The root comes first, followed by a list of sub-trees
data link 1 link 2 ... link n
How many link fields are
needed in such a representation?
( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) )
A
B C
E
F G D
K L
H ( shows left
, shows right
M I
J
Binary Tree Representations in Array
If a complete binary tree with n nodes (depth = log2 (n + 1)-1) is
represented sequentially, then for any node with index i where
1<=i<=n, we have:
parent(i) is at i/2 if i!=1.
If i=1, i is at the root and has no parent.
left_child(i) is at 2i if 2i<=n.
If 2i>n, then i has no left child.
right_child(i) is at 2i+1 if 2i +1 <=n.
If 2i +1 >n, then i has no right child.
[1] A
Sequential Representation [2] B
[3] C
(1) waste space
[4] D
(2) insertion/deletion
A [1] A [5] E
[2] B problem
[6] F
[3] -- [7]
B G
[4] C [8]
A H
[5] -- [9]
C I
[6] --
[7] -- B C
D [8] D
[9] --
. . D E F G
E
[16] E
H I
Tree using Linked List Representation
struct node {
int data;
node* left; data
node* right;
};
left_child right_child
left data right
A Tree can be representing as: data
left child right child
B C D
E F G H I J
K L M
37
t
6 Tree root node
t
2 8 NULL NULL 6
2 8
t
1 NULL NULL 4 NULL 1 4
3 5
3 NULL NULL 5 NULL NULL
New Node
Linked List Representation of Binary Tree
• Double linked list is used to represent a binary tree.
• Most clear representation is:
Binary Search Tree
• A binary tree with the property that items in the left
subtree are smaller than the root and items are larger or
equal in the right subtree is called a binary search tree
(BST).
• The tree we will built for searching for duplicate numbers
will be a binary search tree.
• BST and its variations play an important role in searching
algorithms.
Applications of Binary Trees
• A binary tree is a useful data structure when two-way
decisions must be made at each point in a process.
• For example, suppose we wanted to find all duplicates in
a list of numbers:
14, 15, 4, 9, 7, 18, 3, 5, 16, 4, 20, 17, 9, 14, 5
Applications of Binary Trees
• One way of finding duplicates is to compare each number with all
those that precede it.
14, 15, 4, 9, 7, 18, 3, 5, 16, 4, 20, 17, 9, 14, 5
14, 15, 4, 9, 7, 18, 3, 5, 16, 4, 20, 17, 9, 14, 5
Searching for Duplicates by linked list
• If the list of numbers is large and is growing, this
procedure involves a large number of comparisons.
• A linked list could handle the growth, but the comparisons
would still be large.
• The number of comparisons can be drastically reduced by
using a binary tree.
• The tree grows dynamically like the linked list.
Searching for Duplicates (Steps)
1. The binary search tree is built in a special way.
2. The first number in the list is placed in a node that is
designated as the root of a binary tree.
3. Initially, both left and right subtrees of the root are
empty.
4. We take the next number and compare it with the
number placed in the root.
5. If it is the same, then we have a duplicate.
Searching for Duplicates (Steps ..Cont)
6. Otherwise, we create a new tree node and put the new
number in it.
7. The new node is made the left child of the root node if
the second number is less than the one in the root.
8. The new node is made the right child if the number is
greater than the one in the root.
Searching for Duplicates
14
14, 15, 4, 9, 7, 18, 3, 5, 16, 4, 20, 17, 9, 14, 5
Searching for Duplicates
15 14
15, 4, 9, 7, 18, 3, 5, 16, 4, 20, 17, 9, 14, 5
Searching for Duplicates
14
15
15, 4, 9, 7, 18, 3, 5, 16, 4, 20, 17, 9, 14, 5
Searching for Duplicates
4 14
15
4, 9, 7, 18, 3, 5, 16, 4, 20, 17, 9, 14, 5
Searching for Duplicates
14
4 15
4, 9, 7, 18, 3, 5, 16, 4, 20, 17, 9, 14, 5
Searching for Duplicates
9 14
4 15
9, 7, 18, 3, 5, 16, 4, 20, 17, 9, 14, 5
Searching for Duplicates
14
4 15
9, 7, 18, 3, 5, 16, 4, 20, 17, 9, 14, 5
Searching for Duplicates
7 14
4 15
7, 18, 3, 5, 16, 4, 20, 17, 9, 14, 5
Searching for Duplicates
14
4 15
7, 18, 3, 5, 16, 4, 20, 17, 9, 14, 5
Searching for Duplicates
18 14
4 15
18, 3, 5, 16, 4, 20, 17, 9, 14, 5
Searching for Duplicates
14
4 15
9 18
18, 3, 5, 16, 4, 20, 17, 9, 14, 5
Searching for Duplicates
3 14
4 15
9 18
3, 5, 16, 4, 20, 17, 9, 14, 5
Searching for Duplicates
14
4 15
3 9 18
3, 5, 16, 4, 20, 17, 9, 14, 5
Searching for Duplicates
5 14
4 15
3 9 18
5, 16, 4, 20, 17, 9, 14, 5
Searching for Duplicates
14
4 15
3 9 18
5, 16, 4, 20, 17, 9, 14, 5
Searching for Duplicates
16 14
4 15
3 9 18
16, 4, 20, 17, 9, 14, 5
Searching for Duplicates
14
4 15
3 9 18
7 16
16, 4, 20, 17, 9, 14, 5
Searching for Duplicates
4 14
4 15
3 9 18
7 16
4, 20, 17, 9, 14, 5
Searching for Duplicates
20 14
4 15
3 9 18
7 16
20, 17, 9, 14, 5
Searching for Duplicates
14
4 15
3 9 18
7 16 20
20, 17, 9, 14, 5
Searching for Duplicates
17 14
4 15
3 9 18
7 16 20
17, 9, 14, 5
Searching for Duplicates
14
4 15
3 9 18
7 16 20
5 17
17, 9, 14, 5
Searching for Duplicates
14
4 15
3 9 18
7 16 20
5 17
9, 14, 5
