Difference between revisions of "TADM2E 5.3"
From Algorithm Wiki
(Recovering wiki) |
(Recovering wiki) |
||
| Line 2: | Line 2: | ||
| − | Base case: Tree composed of just two nodes: x(root) and y. There is only one way x - | + | 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 - | + | 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 |
Latest revision as of 18:22, 11 September 2014
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
