Home | | Object Oriented Programming and Data Structures | Properties of binary trees

Chapter: Object Oriented Programming and Data Structure : Non-Linear Data Structures

Properties of binary trees

The number of nodes n in a perfect binary tree can be found using this formula: n = 2h+1-1

Properties of binary trees

• The number of nodes  n in a perfect binary tree can be found using this formula: n = 2h+1-1

where h is the depth of the tree.

• The number of nodes  n in a binary tree of height h is at least n = h + 1 and at most n = 2h+1-1

where h is the depth of the tree.

• The number of leaf nodes l in a perfect binary tree can be found using this formula: l = 2h where h is the depth of the tree.

• The number of nodes n in a perfect binary tree can also be found using this formula: n = 2l-1 where l is the number of leaf nodes in the tree.

 

• The number of null links (i.e., absent children of nodes) in  a complete binary tree of n nodes

is (n+1).

   The number of internal nodes (i.e., non -leaf nodes or n-l) in a complete binary tree of n nodes is n/2 .

 

For any non -empty binary tree with n0 leaf nodes and n2 nodes of degree 2, n0 = n2 + 1.[6]


Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail
Object Oriented Programming and Data Structure : Non-Linear Data Structures : Properties of binary trees |


Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2023 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.