[18]
The classes
MyBinaryTreeNode and
MyBinaryTree
are given below.
Objects of type MyBinaryTree
are linked binary trees.
public class MyBinaryTreeNode
{
Object element;
BinaryTreeNode leftChild; // left subtree
BinaryTreeNode rightChild; // right subtree
}
public class MyBinaryTree
{
BinaryTreeNode root; // root node
// code you write will come here
}
You are to write a public method maxHeightDifference().
The invocation x.maxHeightDifference()
returns
0
if the binary tree x
is empty;
otherwise, it returns
the maximum difference in the heights of the left and right subtrees
of any node in the tree.
x.maxHeightDifference() = maxy is a node of x {|height(left subtree of y)
- height(right subtree of y)|}
- (a)
-
[16]
Write Java code for the public method
maxHeightDifference.
You may define, implement and create additional
methods and variables as needed.
You may use Java's methods Math.max
and Math.abs. Math.max(a,b)
returns the larger of a and b,
and Math.abs(a) returns the absolute value of
a.
You may not create any new nodes, new instances
of MyBinaryTree, or invoke any methods
(other than Math.max
and Math.abs)
for which you have not provided code.
(Hint: use recursion.)
- (b)
-
[2] What is the time complexity of your code as a function
of the number of nodes in the binary tree?