- A tree whose elements have at most 2 children is called a binary tree.
- Each element of a binary tree can have only 2 children, we name them the left and right child.
- The height of a binary tree is equal to the largest number of edges from the root to the most distant leaf node.
begin height(root)
If node is NULL
then return 0
Else
If left child and right child nodes are NULL
return 1
Else
take two integers let 'l' and 'r' to store value of left child and right child recursively
by using formula:
height_of_a_tree = 1 + (which-one is bigger from 'l' & 'r')
end height
100
\
120
\
130
\
140
\
150
\
160
\
170
Height of tree: 7
100
/ \
30 150
/ \ / \
20 50 122 188
Height of tree: 3
- Time Complexity: O(n)
- Space Complexity: O(n)
- A node is a leaf node if both left child and right child nodes of its are NULL.
- We are using Recursion to count nodes.
begin leaf_count(root)
If node is NULL
then return 0
Else
If left child and right child nodes are NULL
return 1
Else
recursively calculate leaf count of the tree using formula:
Leaf_count_of_tree = Leaf_count_of_left_subtree + Leaf_count_of_right_subtree
end leaf_count
100
\
120
\
130
\
140
\
150
\
160
\
170
No. of leaf nodes of tree: 1
30
/ \
20 40
/ \ / \
10 25 35 45
No. of leaf nodes in tree: 4
- Time Complexity: O(n)
- Space Complexity: O(n)