Properties of Binary Trees

Prerequisites

Trees Show

Binary Trees Show

Properties of Binary Trees

Introduction

  • A binary tree is a type of tree in which each each node has at most two child branches.
  • This article lists its various properties.

Notation

  • n is the number of nodes.
  • nk is the number of nodes with degree k.

n = n0 + n1 + n2

  • Any node in a binary tree will have a degree of 0, 1, or 2.
  • The total number of nodes is equal to the number of nodes with degrees 0, 1, and 2.

The number of branches is n - 1

  • Each node in the tree (except the root) will will have a branch leading to it.

The number of branches is equal to n1 + 2n2

  • Each node has k branches extending from it (where k is the degree of the node).
  • There will be a total of n1 branches extending from the nodes with degree 1.
  • There will be a total of 2n1 branches extending from nodes with degree 2.

n0 = n2 + 1

  • The number of vertices of degree 2 is always 1 more than the number of vertices of degree 0.
  • Proof:
    • We know that the number of branches is n - 1 and that:
      n = n0 + n1 + n2
    • Therefore the number of branches is:
      n0 + n1 + n2 - 1
    • We also know that the number of branches is:
      n1 + 2n2
    • Therefore:
      n1 + 2n2 = n0 + n1 + n2 - 1
    • This simplifies to:
      n0 = n2 + 1
  • Implications:
    • n0 and n2 are not relative to n1
    • You can add and remove nodes with degree 1 without affecting n0 or n2

The maximum number of nodes at level i is 2i

  • The number of nodes at any level is at most twice as many as at the previous level.

The maximum number of nodes in a tree with height k is 2k+1 - 1

  • Prerequisites:
    • The proof of a binary summation being equal to one less than the next in the series
  • At each level between 0 and k, the maximum number of nodes is 2k
  • Summing these together gives:
    2k+1 - 1

The maximum height of a tree with n nodes is n - 1

  • In the worst case scenario a skewed tree would have one node at each level
  • There would be n levels
  • The distance between the bottom level and the root would be n - 1

The minimum height of a tree with n internal nodes is log2(n + 1)

  • In the best case scenario, the nodes will be arranged as a full tree.
  • We know that the maximum number of nodes at the bottom level is 2h
    • These are external nodes
  • We also know that there are n + 1 external nodes
  • Therefore we can assert: n + 1 ≤ 2h
  • If we take the log of both sides then log2(n + 1) ≤ h