Data structure in java I. Given a binary tree of integers write a routine which
ID: 3908155 • Letter: D
Question
Data structure in java I. Given a binary tree of integers write a routine which will accept a pointer to the tree, traverse the entire tree and return a pointer to the smallest element (the element whose info field contains the smallest integer) of the tree as well as the number of nodes in the tree that have both right and left sons. Given a singularly linked list write a routine which will read the information field of each node (which is an integer) and create two separate singularly linked lists. One list will be made up of all the nodes whose information field contains an even integer and the second list will be made up of all the nodes whose information field contains an odd integer.
Explanation / Answer
Answer I
========
The following code is in java assuming a Node class with getLeft() and getRight() methods to fetch the children
//method to return the smallest node in hte binary tree
Node smallest(Node root)
{
if(n == null)
return null;
else
{
Node curr = root;
while(curr.getLeft() != null)
curr = curr.getLeft();
return curr;
}
}
//method to count non-leaf nodes
int countNonLeaf(Node n)
{
if(n == null )
return 0;
int count = countNonLeaf(n.getLeft()) + countNonLeaf(n.getRight());
if(n.getLeft() != null && n.getRight() != null)
{
count = count + 1;
}
return count;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.