Binary Search Tree
A binary tree is a set of finite sets of nodes that is empty or consists of root and two disjoint binary trees called the left and right subtree. The left or right subsets are themselves binary trees. A left or right sub tree can be empty.
- The left subtree of a node contains only nodes with keys lesser than the node’s key.
- The right subtree of a node contains only nodes with keys greater than the node’s key.
- The left and right subtree each must also be a binary search tree.
Types of Binary Tree:
1. Left aligned Binary tree:
2. Right aligned Binary tree:
3. Complete Binary tree:
4. Left Heavy:
The maximum number of nodes on level i of a binary tree is 2i. For the shown binary tree number
of nodes on each level are:
Nodes at level 2 → 22
= 4
Nodes at level 1 → 21
= 2
Nodes at level 0 → 20
= 1
The maximum number of nodes in a binary tree of depth k is 2k where k > 0.
If a binary tree contains ‘m’ nodes at level ‘L’, then it contains at most ‘2m’ nodes at level ‘L+1’.
Therefore, total number of nodes in complete binary tree is
n = 20 + 21 + 22 +⋅⋅⋅⋅⋅⋅+ 2d = 2(d+1) –1
NOTE : If you fined any mistake or weakness in my article please help us to improve our content.
Also Read Our Best Article on Networking :
