Counting nodes in binary trees

ABSTRACT

This paper describes an original method for introducing linear recurrence relations. Boolean expressions are represented by binary trees and the counting of the internal nodes of these trees yield linear recurrence relations. The method allows the students to create their own family of Boolean expressions, to draw the corresponding binary trees, to deduce the recurrence relation representing the number of nodes in the trees, and finally, to solve and check the solutions of these relations.

REFERENCES

• Li77: C. L Liu, Elements of discrete mathematics (McGraw-Hill computer science series), McGraw-Hill Pub. Co., 1977
• Pu85: Paul Walton Purdom, Jr. , Cynthia A. Brown, The analysis of algorithms, Holt, Rinehart & Winston, Austin, TX, 1985
• Ta81: A. S. Tanenbaum, Computer networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988

INDEX TERMS

Classification:
  E. Data

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Algorithms