Scribd
Upload
63 views3 pages

Data Structures and Algorithms Winter Term 2010-2011: Quiz 3

This document is a quiz for a data structures and algorithms course. It contains instructions for students, outlines two exercises to be completed, and provides space for students to write their name, application number, and group number. The first exercise involves drawing a binary search tree by inserting elements in a given order. The second exercise asks students to write a recursive method that returns the maximum cost of a root-to-leaf path in a sample tree containing positive integers.

Uploaded by

AhmedSerag
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
63 views3 pages

Data Structures and Algorithms Winter Term 2010-2011: Quiz 3

This document is a quiz for a data structures and algorithms course. It contains instructions for students, outlines two exercises to be completed, and provides space for students to write their name, application number, and group number. The first exercise involves drawing a binary search tree by inserting elements in a given order. The second exercise asks students to write a recursive method that returns the maximum cost of a root-to-leaf path in a sample tree containing positive integers.

Uploaded by

AhmedSerag
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

Page 0

German University in Cairo


Media Engineering and Technology
Prof. Dr. Slim Abdennadher
Assoc. Prof. Dr. Georg Jung

December 27, 2010

Data Structures and Algorithms


Winter term 2010-2011
Quiz 3
Version I

Name:

............................................................................................

Application Number:

Group:

...............................................................................

.............................................................................................

Instructions: Read carefully before proceeding.


1) Write your name, application number, and group number in the space provided above.
2) No books or other aids are permitted for this test.
3) When you are told that time is up, stop working on the test.
Good Luck!

Dont write anything below ;-)


Exercise
Possible Marks
Final Marks

1
2

2
8

P
10

Data Structures and Algorithms, Quiz 3, December 27, 2010

Exercise 1

Page 1

(2 Marks)

Draw a binary search tree by inserting the following elements in the given order: 50, 90, 30, 110, 70, 40, 10.
Solution:
o 50 OOOO
ooo
OOO
o
o
OOO
oo
o
o
OOO
wooo
'
30 ?
90 =
?
==


??


==


?


==
??






10
40
70
110

Data Structures and Algorithms, Quiz 3, December 27, 2010

Exercise 2

Page 2

(8 Marks)

A root-to-leaf path is a sequence of nodes in a tree starting from the root node and proceeding downward to a leaf
(a node with no children). An empty tree contains no root-to-leaf paths. The cost of a path is the summation of the
values of a path. For example, the following tree has exactly four root-to-leaf paths:

}
}}
}
}}
~}
}
11 A
AA
}}
AA
}
}
AA
}
}
A
}
~
}

The root-to-leaf paths are:


5 4 11 7
5 4 11 2
5 8 10 1
584

ll 5 PPPPP
lll
PPP
l
l
PPP
lll
l
l
PPP
ll
l
P(
l
vl
8C
}} CCCC
}
}
CC
}}
CC
~}}
!
10 A
4
AA
AA
AA
A
1

cost = 27
cost = 22
cost = 24
cost = 17

Write an internal method int maxPathCost() that returns the cost of the root-to-leaf path with the maximum
cost. Assume that the tree contains only positive integers and that the tree nodes contain data which is of type int.
Thus the implementation of the Node class is as follows:
class Node {
int data;
Node left, right;
}

For example, for the tree above, your method should return 27.
Note: Your solution MUST be implemented recursively.
Solution:
public int maxPathCost() {
return maxPathCost(root);
}
public int maxPathCost(Node node) {
if (node == null)
return 0;
return node.data + Math.max(maxPathCost(node.left), maxPathCost(node.right));
}

You might also like