Difference between revisions of "7.3"

From The Algorithm Design Manual Solution Wiki
Jump to navigation Jump to search
(Created page with "Induction proof: Base case: Tree composed of just two nodes: x(root) and y. There is only one way x -> y Assuming there is an unique path between x and y, we add a new leaf...")
 
(No difference)

Latest revision as of 01:00, 21 September 2020

Induction proof:


Base case: Tree composed of just two nodes: x(root) and y. There is only one way x -> y

Assuming there is an unique path between x and y, we add a new leaf z under y. z is only connected to its parent y, so there is only one way from z to x that is z -> y->[unique path assumed]->x


Back to Chapter 7