Problem 1
Input
Binary tree T
Out
True if the tree is BST, False otherwise
Incorrect Solution
function Check(T):
if T = null:
return True
return Check(T.left)
and Check(T.right)
and (T.key < T.right.key)
and (T.key > T.left.key)
This is wrong because it only compares node with its direct children, but it doesn't check the grandchildren.
Idea
Check T.key > max(T.left) and T.key < min(T.right)
Solution
function Check2(T):
if T = null:
# return (True, -inf, inf) # WRONG!!
return (True, inf, -inf)
res1, minl, maxl = Check2(T.left)
res2, minr, maxr = Check2(T.right)
res = resl and res r
and T.key > maxl and T.key < minr
_min = min(minl, minr, T.key)
_max = max(maxl, maxr, T.key)
return res, _min, _max
Complexity
Single Call:
number of calls = n + #Nulls 3n
Total:
Exercise
CHECK IF RB-TREE
Stock Price
Input
Given stock prices P[1..n]
Output
Days to buy and sell to maximize profit given $1 fee for each day of owning the seock. Complexity
Example
P = [1,3,3,4]
buy = 1
sell = 1
profit = 3 - 1 = 2
Divide & Conquer
From recursive call
- buy&sell in 1st half
- buy&sell in 2nd half
To consider
- buy in 1st and sell in 2nd
if there is not $1 fee, the profit is max(P[n/2:]) - min(P[n/2])
max(P[k]-(k-n/2) | k from n/2+1 to n)
+
max(-P[l]-(n/2-l) | l from 1 to n/2)
Solution
function SellBuy(P):
if n = 1:
return 0
m = int(n/2)
left = SellBuy(P[1..m])
right = SellBut(P[m+1..n])
middle = ...
return max(left, right, middle)x
Problem 3
Input
Array A[1..n] of numers and number C
Output
-
Trueif there areiandjsuch thatA[i] + A[j] = C -
Falseotherwise
Complexity:
Steps
- Sort
A - For every
i, search for(C-A[i])/2. If found returnTrue - return
False
?? :triangular_flag_on_post:: do 2 in
Dream
For every i, search for (C-A[i])/2 in A[i+1..n]
- RB-tree T empty
- For every
ifromnto1- search
(C-A[i])/2in T, returnTrueif found - insert
A[i]ino T
- search
- return
False
If we have no duplicates,
sort array of paris (A[i],i) by i
?? :triangular_flag_on_post:: What if we want to count # of such (i,j)
