Page 537 - Computer science 868 Class 12
P. 537
• Height of a tree: It is the length of the longest path from the leaf node to the root of the tree. For a tree, it’s height
and depth are same.
Height of a node is, however, different from its depth. Height of a node is the longest path from the leaf node to the
given node.
Thus, height of root node 8 is 4.
Height of nodes 3 and 10 is 3.
Height of nodes 1, 6 and 15 is 2.
Height of nodes 4, 7, 13 is 1.
The difference between depth and height is that in the former the counting starts from the root (top to bottom)
while in the later it starts from the leaf (bottom to top).
• Forest: A set of disjoint trees is called a forest. If the root node is removed from a tree then a forest is formed.
3 10
1 6 15
4 7 13
13.4.3 Binary Tree
A binary tree is a tree structure where the degree is 2. A binary tree has maximum of two children. The following are
the properties of a Binary tree.
1. A binary tree can have only one root node.
2. A node can contain 0, 1 or 2 child nodes.
3. A node can have only one parent node.
All the examples given above are of a binary tree.
Binary Search tree (BST): It is a special type of binary tree which has the following properties.
1. Value of the left node is always less than its parent node.
2. Value of the right node is always greater than its parent node.
3. BST reduces the search time and is widely used in searching and sorting.
Balancing a binary tree: A binary tree is said to be balanced if the difference of height of its left sub tree and right sub
tree is less than or equal to 1. Some examples are given below.
Example 1:
3
Height of the left sub tree is 2
Height of the right sub tree is 3
1 6
Difference in height is 1.
So, this tree is balanced.
4 7
535
Data Structures 535

