A binary tree can be represented as a list of nodes where each node has three pa
ID: 667762 • Letter: A
Question
A binary tree can be represented as a list of nodes where each node has three parts:
- a data part which holds the value stored in the node;
- a left field which has the index for the node in the list which is the root of the left subtree;
- a right field which has the index of the node in the list which is the root of the right subtree.
We can use the following notation when describing nodes in List:
List [ 4 ] – is the fifth node in the list. It has data, left and right fields.
List [ 4 ].data is the data field of the fifth node in List.
List [ 4 ].left is the index of the node in list which is the root node for the left subtree.
List [ 4 ].right is the index of the node in list which is the root node for the right subtree.
If a left or right field has the special value, NULL, then it means there is no corresponding binary tree.
(a) Show how the following binary trees would get represented using this list form:
(i) a binary tree which consists of one data value, Fred
(ii) a binary tree whose root has the data value +, whose left subtree only has the value a and whose right subtree only has the value b
(iii) a binary tree whose root has the value *, whose left subtree has the value C and whose right subtree is the binary tree from (ii).
(b) Consider the following module for manipulating binary trees:
Module Find_Value ( List, Root, Value ) {
If ( Root is NULL )
{
Return NULL
}
Else
{
If ( List [ Root ] .data equals Value )
Return Root
Temp = Find_Value ( List, List[ Root ].left, Value )
If ( Temp is NULL )
Return Find_Value ( List, List[ Root ].right, Value )
else
Return Temp
}
}
Trace the execution and show what output is produced when List contains the binary tree for (iii) in part (a) of this question, and the value it is looking for is b. This corresponds to the call
Find_Value( List, 0, b ).
Your answer should show each call on a module, the parameters that are involved in the call and the result that each module call returns.
(c) Write a module called
Module Find_Latest_Common_Ancestor ( List, Root, Value1, Value2 )
This Module is given a binary tree stored in List. The index in List of the root node for the tree is given in Root while Value1 and Value2 are two values. If neither value is in the binary tree, the module should return the result, NULL. If both values are in the tree, the module should return the index of the deepest node in the tree that has Value1 and Value2 in its subtrees.
Node1 is deeper in the binary tree than Node2 if the path from the root node to Node1 is longer than the path from the root node to Node2.
Your Module should use the Find_Value module from part (b).
Pls write in Pseudo Code form, thx
Explanation / Answer
(a) Show how the following binary trees would get represented using this list form:
(i) a binary tree which consists of one data value, Fred
List[0].data = “Fred”
(ii) a binary tree whose root has the data value +, whose left subtree only has the value a and whose right subtree only has the value b
List[0].data = “+”
List[0].left = “a”
List[0].right = “b”
Node2 = List[0]
(iii) a binary tree whose root has the value *, whose left subtree has the value C and whose right subtree is the binary tree from (ii).
List[0].data = “*”
List[0].left = “C”
List[0].right = Node2
(b) Consider the following module for manipulating binary trees:
Module Find_Value ( List, Root, Value ) {
If ( Root is NULL ){ Return NULL}
Else{If ( List [ Root ] .data equals Value ) Return Root
Temp = Find_Value ( List, List[ Root ].left, Value )
If ( Temp is NULL ) Return else Return Temp
} // end else
} // end module
Trace the execution and show what output is produced when List contains the binary tree for (iii) in part (a) of this question, and the value it is looking for is b. This corresponds to the call
Find_Value( List, 0, b ).
Your answer should show each call on a module, the parameters that are involved in the call and the result that each module call returns.
Execution Trace:
Values assigned by the call Find_Value(List,0,b) to Module Find_Value ( List, Root, Value )
List = List; Root = 0; Value = b
Root = 0 = not Null hence will get to the else part
List[0].data = * != data b hence it will call again as
Temp = Find_Value ( List, List[ Root ].left, Value ) values assigned will be
Root = List[Root].Left = List[0].left = C since root is not null it will again call as Find_Value ( List, List[ Root ].left, Value ) where Root = C.left = NULL
since Root = NULL, it will return NULL then the
recursion traces back for each call which assigns the value NULL to Temp
if Temp is NULL it will call Find_Value ( List, List[ Root ].right, Value )
where Root = + since root is not null and is not equal to the value b, it will call
Temp = Find_Value ( List, List[ Root ].left, Value )
where Root = a
It will do the same and will call right from + where Root = b
It will satisfy the statement If ( List [ Root ] .data equals Value ) Return Root
and will return the value b
(c)
// in order to find the depth we need to make a small change in the Find_Value module by introducing a depth count and call it as Find_Value_With_Depth as follows:
static int depth;
Find_Value_With_Depth ( List, Root, Value ) {
depth++
// increment depth for each recursive call
//the value with higher value of depth is the deepest for example a is deeper than C
If ( Root is NULL ){ Return NULL}
Else{If ( List [ Root ] .data equals Value ) Return Root
Temp = Find_Value_With_Depth ( List, List[ Root ].left, Value )
If ( Temp is NULL ) Return else Return Temp
} // end else
} // end module
Writing a module called
Module Find_Latest_Common_Ancestor ( List, Root, Value1, Value2 )
our Module uses the Find_Value module from part (b).
Module Find_Latest_Common_Ancestor(List Root, Value1, Value2) {
Declare variable depth1, depth2 as integers; // int depth1, depth2;
if ( (Find_Value(List, Root, Value1) = NULL ) AND (Find_Value(List, Root, Value2) = NULL ) ) { Return NULL; } // neither value is in the tree hence return null
If ( ( Find_Value(List, Root, Value1) == Value1 ) AND ( Find_Value(List, Root, Value2) == Value2 )
{ // both the values are there in the tree hence will deepest node by using depth
assign depth = to value 1
call module Find_Value_With_Depth(List, Root, Value1);
let depth1 = depth;
let depth = 1
call module Find_Value_With_Depth(List, Root, Value2);
let depth2 = depth;
if (depth1 > depth2) { return Value1}
// value1 is the deepest and it is the latest common ancestor
if (depth2 > depth1) {[ return Value2}
// value2 is the deepest and it is the latest common ancestor
} // end Module Find_Latest_Common_Ancestor
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.