Trees & Binary Trees
Tree: A tree is non-linear and a hierarchical data structure consisting of a collection of nodes such that each
node of the tree stores a value and a list of references to other nodes (the “children”).
This data structure is a specialized method to organize and store data in the computer to be used more
effectively. It consists of a central node, structural nodes, and sub-nodes, which are connected via edges. We
can also say that tree data structure has roots, branches, and leaves connected with one another.
Node: It represents a termination point in a tree.
Root: A tree’s topmost node.
Parent: Each node (apart from the root) in a tree that has at least one sub-node of its own is called a parent
node.
Child: A node that straightway came from a parent node when moving away from the root is the child node.
Leaf Node: These are external nodes. They are the nodes that have no child.
Internal Node: As the name suggests, these are inner nodes with at least one child.
Depth of a Tree: Total number of edges from root node to a particular node is called as depth of that node.
Depth of a tree is the total number of edges from root node to a leaf node in the longest path.
Depth of the root node = 0
The terms “level” and “depth” are used interchangeably.
Height of a Tree: Total number of edges that lies on the longest path from any leaf node to a particular node
is called as height of that node.
Height of a tree is the height of root node. Height of all leaf nodes = 0
Degree: Degree of a node is the total number of children of that node.
Degree of a tree is the highest degree of a node among all the nodes in the tree.
Binary Tree
The Binary tree means that the node can have maximum two children. Here, binary name itself suggests that
'two'; therefore, each node can have either 0, 1 or 2 children.
The above tree is a binary tree because each node contains the atmost two children.
Binary Tree Representation
A node of a binary tree is represented by a structure containing a data part and two pointers to other structures
of the same type.
In the above tree, node 1 contains two pointers, i.e., left and a right pointer pointing to the left and right node
respectively. The node 2 contains both the nodes (left and right node); therefore, it has two pointers (left and
right). The nodes 3, 5 and 6 are the leaf nodes, so all these nodes contain NULL pointer on both left and right
parts.
Properties of Binary Tree
o At each level of i, the maximum number of nodes is 2i.
o The height of the tree is defined as the longest path from the root node to the leaf node. The tree which
is shown above has a height equal to 3. Therefore, the maximum number of nodes at height 3 is equal to
(1+2+4+8) = 15. In general, the maximum number of nodes possible at height h is (2 0 + 21 + 22+….2h) =
2h+1 -1.
o The minimum number of nodes possible at height h is equal to h+1.
o Number of edges: An edge can be defined as the connection between two nodes. If a tree has N nodes
then it will have (N-1) edges. There is only one path from each node to any other node of the tree.
o Depth of a node: The depth of a node is defined as the length of the path from the root to that node.
Each edge adds 1 unit of length to the path. So, it can also be defined as the number of edges in the
path from the root of the tree to the node.
o Height of a node: The height of a node can be defined as the length of the longest path from the node
to a leaf node of the tree.
o Height of the Tree: The height of a tree is the length of the longest path from the root of the tree to a
leaf node of the tree.
o Degree of a Node: The total count of subtrees attached to that node is called the degree of the node.
The degree of a leaf node must be 0. The degree of a tree is the maximum degree of a node among all
the nodes in the tree.
If there are 'n' number of nodes in the binary tree.
The minimum height can be computed as:
As we know that,
n = 2h+1 -1
n+1 = 2h+1
Taking log on both the sides,
log2(n+1) = log2(2h+1)
log2(n+1) = h+1
h = log2(n+1) - 1
The maximum height can be computed as:
As we know that,
n = h+1
h= n-1
Types of Binary Tree
There are Six types of Binary tree:
o Full/ proper/ strict Binary tree
o Complete Binary tree
o Perfect Binary tree
o Skew Binary Tree
o A degenerate Tree
o Balanced Binary Tree
1. Full/ proper/ strict Binary tree
The full binary tree is also known as a strict binary tree. The tree can only be considered as the full binary tree if
each node must contain either 0 or 2 children. The full binary tree can also be defined as the tree in which each
node must contain 2 children except the leaf nodes.
Examples:
2. Complete Binary Tree
The complete binary tree is a tree in which all the nodes are completely filled except the last level. In the last
level, all the nodes must be as left as possible. In a complete binary tree, the nodes should be added from the
left.
Examples:
3. Perfect Binary Tree
A tree is a perfect binary tree if all the internal nodes have 2 children, and all the leaf nodes are at the same
level.
4. Skewed Binary Tree
A skewed binary tree is a pathological/degenerate tree in which the tree is either dominated by the left nodes or
the right nodes. Thus, there are two types of skewed binary tree: left-skewed binary tree and right-skewed
binary tree.
Left Skewed Binary Tree: If all nodes are having a left child or no child at all then it can be called a left
skewed binary tree. In this tree all children at right side remain null.
Right Skewed Binary Tree: If all nodes are having a right child or no child at all then it can be called a right
skewed binary tree. In this tree all children at left side remain null.
5. A degenerate (or pathological) tree:-
A Tree where every internal node has one child. Such trees are performance-wise same as linked list.
A degenerate or pathological tree is the tree having a single child either left or right.
6. Balanced Binary Tree
It is a type of binary tree in which the difference between the height of the left and the right subtree for each
node is either 0 or 1.
