CODEWITHSUNDEEP
data-structures
Krishna Kumar
Krishna Kumar

Reputation: 11

Minimum number of vertices in a binary tree of height 5

What is the Formula to Find the minimum number of vertices required to make a binary tree (not a complete binary tree) of height 5 ?

Upvotes: 1

Views: 3990

Answers (2)

Amnon
Amnon

Reputation: 325

the minimum number of vertices in a binary tree of height n (with no further constraints) is always n.

proof:

  1. if there were less than n nodes, the tree wouldn't be a valid binary tree (I guess I don't need to further explain this point)
  2. if there were more than n nodes, it means at least one of the nodes has a brother (pigeonhole principle), which could be taken off the tree and it would result in a valid, smaller binary tree, so we know that this tree is not minimal, which opposes our assumption of a minimal tree. -> a binary tree T is minimal -> T has n nodes

Upvotes: 1

Lionel
Lionel

Reputation: 136

A binary tree's height cannot be bigger than the number of nodes or vertices in the tree. So yes, the minimum number of vertices required for a binary tree of height 5 will be 5. Also, there must be n-1 edges between them. You can imagine a single series of connected nodes, and that is basically what you get.

Alternately, a full binary tree is a binary tree in which each internal vertex has exactly two children.This means a binary tree with n internal vertices has 2n + 1 vertices, 2n edges, and n + 1 leaves.

Upvotes: 1

Related Questions