Question on Binary tree

  • Thread starter algonewbee
  • Start date
  • #1
algonewbee
The internal path length of a full binary tree is the sum, taken over all internal nodes of the tree, of the depth of each node. Likewise, the external path length is the sum, taken over all leaves of the tree, of the depth of each leaf. Consider a full binary tree with n internal nodes, internal path length i, and external path length e. Prove that e=i+2n
 

Answers and Replies

  • #2
695
2
Ask yourself what does it mean for the tree to be "full". How many leaves does it have?

Probably this should not be in the number theory forum.
 

Related Threads on Question on Binary tree

  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
9
Views
17K
  • Last Post
Replies
3
Views
6K
  • Last Post
Replies
3
Views
3K
  • Last Post
Replies
4
Views
3K
  • Last Post
Replies
11
Views
3K
Replies
6
Views
722
  • Last Post
Replies
2
Views
4K
Replies
1
Views
2K
  • Last Post
Replies
1
Views
2K
Top