Binary
Search Trees (BST)
Problem 2:
Add the
following methods in Tree.java and test the same in TreeTest.java:
a)
A method
which takes the address of the root as the input and returns the height of the
BST.
The height of a BST = 1 + Maximum of (height of the left sub tree,
height of the right sub tree)
b)
Write
a method which outputs the values of the deepest leaf/leaves in the binary
search tree.
c)
Write
a method which outputs the values in the binary search tree in increasing order.
d)
Write a method which prints the values in the binary search tree by
level. Start by printing the value of the root (level = 1) and then values at
level = 2, level = 3 and so on.
The above
methods have been added to Tree.java:
·
Node.java will remain unchanged.
Example:
1 - Insert a
Value
2 - Print
the Tree
3 - Height
4 - Deepest
Leaf/Leaves
5 -
Increasing Order
6 - Output
by Level
7 – Non leaf
node values
8 - Quit
2
90
43
23
3
2
1
0
-1
1 - Insert a
Value
2 - Print
the Tree
3 - Height
4 - Deepest Leaf/Leaves
5 -
Increasing Order
6 - Output
by Level
7 – Non leaf
node values
8 - Quit
3
The height
of the tree is 4
1 - Insert a
Value
2 - Print
the Tree
3 - Height
4 - Deepest
Leaf/Leaves
5 -
Increasing Order
6 - Output
by Level
7 – Non leaf
node values
8 - Quit
4
The deepest
leaf/leaves are:
2
90
1 - Insert a
Value
2 - Print
the Tree
3 - Height
4 - Deepest
Leaf/Leaves
5 -
Increasing Order
6 - Output
by Level
7 – Non leaf
node values
8 - Quit
5
The values
in increasing order:
-1 0 1
2 3 23 43 90
1 - Insert a
Value
2 - Print
the Tree
3 - Height
4 - Deepest
Leaf/Leaves
5 -
Increasing Order
6 - Output
by Level
7 – Non leaf
node values
8 - Quit
6
Printing the
values by Level:
Level 1:
1
Level 2:
0 23
Level 3:
-1 3
43
Level 4:
2 90
1 - Insert a
Value
2 - Print
the Tree
3 - Height
4 - Deepest
Leaf/Leaves
5 -
Increasing Order
6 - Output
by Level
7 – Non leaf
node values
8 - Quit
7
The non-leaf
node values are:
1
0
23
3
43
1 - Insert a
Value
2 - Print
the Tree
3 - Height
4 - Deepest
Leaf/Leaves
5 -
Increasing Order
6 - Output
by Level
7 – Non leaf
node values
8 - Quit
8
End of
Program