Tree : undirected, connected, cycless graph
←→ undirected, there exists 1 path between any nodes u,v
Free tree
Parent, children, sibling
Nonterminal node ( internal )
Height
Internal path length, I= 0 + 1 + 1 + 1 + 2
External path length, E= 2 + 3 + 2 + 1 + 2 + 2
→ (1) N + 1 external nodes
(2) E = I + 2N
proof : (1) external ←→ player
internal ←→ game
(2) E = I + ( #edges )
2 → E
1 → I