Saturday, 17 March 2018

Binary tree and its properties in data structures

Binary tree and its properties


Binary tree

A tree that can have at most two children (left and right) for each node (internal) is called binary tree.

Properties of binary tree


  • A binary tree can be either empty (without any nodes), or consists of only one node (root node), or consists of a root node with two binary sub-trees called left sub-tree and right sub-tree.
  • A binary tree with no nodes is called NULL tree.
  • If h is the height of a binary tree,
    • The tree can have maximum of 2h leaf nodes (leaves).
    • The tree can have maximum of 2h+1-1 nodes (internal+external nodes)
    • The minimum number of nodes is h+1.
  • Minimum number of levels of a binary tree with N nodes is log2N+1 (flooring of log2N+1)
  • A binary tree with L leaves have at least ⌊log2L⌋+1 levels
Example:
All trees given in the following picture are binary trees;




Height of binary tree (a) is 1, (b) is 1, (c) is 2, (d) is 2, (e) is 1, (f) is 2, and (g) is 2.
Minimum number of nodes of a tree of height h is h+1. Hence, a tree of height 0 must have at least 1 node (0+1), a tree of height 1 must have at least 2 nodes (1+1), a tree of height 2 must have at least 3 nodes (2+1). For example, trees (a) and (b) both of height 1 have two nodes, trees (c) and (d) both of height 2 and have 3 nodes etc.
Maximum number of nodes in a binary tree can be 2h+1-1. In our example, binary tree (e) and (g) has maximum number of nodes. For (e), height is 1, so 21+1-1 = 3 nodes. For (g), height is 2, so 22+1-1 = 7 nodes.
Minimum number of levels of a binary tree with 2 nodes (figure (a) and (b)) should be at least log2N + 1, that is, 1 level. For the example in figure (g), the minimum number of levels is log27⌋ + 1 = ⌊1.946⌋ + 1 = 1+1 = 2. [Note: use ln function in calculator]


*************

Go to Types of Binary Tree page



binary tree and its properties
height of a binary tree
minimum levels in a binary tree
minimum number of nodes in a binary tree
maximum number of nodes in a binary tree
binary tree examples












No comments:

Post a Comment

SQL exercises for beginners one

SQL Exercises for Beginners / Simple SQL Exercises with Answers / Solved SQL exercises / SQL solved exercises with simple conditions / So...