The other two subset are themselves binary trees, called the left and right sub trees of the original tree.
A left or right sub tree can be empty. Each element of a binary tree is called a node of the tree.
In computer science, a binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.
Types of Binary Trees
- Strictly Binary Tree
- Complete Binary Tree
- Almost Complete Binary Tree
Strictly Binary Tree
If every non-leaf node in a binary tree has nonempty left and right subtrees, the tree is termed a strictly binary tree. Or, to put it another way, all of the nodes in a strictly binary tree are of degree zero or two, never degree one.
Complete Binary Tree
Almost Complete Binary Tree
- Any node nd at level less than d-1 has two sons.
- For any node nd in the tree with a right descendant at level d, nd must have a left son and every left descendant of nd is either a leaf at level dd or has two sons.
- The nodes of an almost complete binary tree are numbered in a way that the root is assigned the number 1, a left son is assigned twice the number assigned to its father, and a right son is assigned one more than twice the number assigned to its father.