Binary Tree | Introduction

Updated: Jun 29

A tree in which each node has at most two children, which are referred to as the left child and the right child.

There we can say that a binary tree node contains the following parts:

  • Data

  • Pointer to the left child

  • Pointer to the right child

Properties of Binary Tree:


  1. Property_01: Minimum number of nodes in the binary tree of height H = H+1

Property_1(Binary Tree)

2. Property_02:

Maximum no of nodes in a binary tree of height H = 2^(H+1)-1


Example:

Maximum number of nodes in a binary tree of height 2

= 2^(2+1) - 1

= 8 - 1

= 7


Thus, in a Binary tree of height = 2, the maximum number of nodes that can be inserted = 7.


Property_2 (Binary Tree)

3. Property_03:

Total number of leaf nodes in a Binary Tree

= Total number of nodes with 2 children + 1


Example:

Consider the following binary tree-


Property_3 (Binary Tree)

Here,

Number of leaf nodes = 4

Number of nodes with 2 children = 3


Clearly, the number of leaf nodes is greater than the number of nodes with 2 children.


4. Property_04:

Maximum number of nodes at any level 'L' in a binary tree = 2^L


Example:

The maximum number of nodes at level 2 in a binary tree.

= 2^2

= 4

Thus, in a binary tree, the maximum number of nodes that can be present at level 2 = 4


Property_4 (Binary Tree)

Follow us on Instagram @programmersdoor

Join us on Telegram @programmersdoor


Please write comments if you find any bug in the above code/algorithm, or find other ways to solve the same problem.

Follow Programmers Door for more.

#blog #interview #placement #learn #computer #science

        Contact Us

programmersdoor@gmail.com

  • LinkedIn
  • Facebook
  • Instagram

©2023 by Programmers Door