Answered step by step
Verified Expert Solution
Question
1 Approved Answer
We are given a binary tree T with n nodes, where each node r has a colour field c[x] which is either blue or red.
We are given a binary tree T with n nodes, where each node r has a colour field c[x] which is either blue or red. For any pair of nodes x and y in T, let path(x,y) denote the unique simple path between them (.e., up from x, along its ancestral path, to the nearest common ancestor of x and y, then down to y, along ancestral path of y). We define the blue-red difference of this path, denoted BRdiff(x, y), to be the number of blue nodes minus the number of red nodes on the path. We want to compute max{ BRdiff(x,y) | XET, YET } We intend to solve this problem in O(n) time by a post-order traversal of T with appropriately strengthened post-condition. Suppose our recursive post-order algorithm is Optimum_Path_BRdiff(r) that is initially invoked at node r = root[T]. The Post-Condition for this recursive call says among the returned values we have O a. 1. MaxPair = maximum BRdiff between any pair of descendants of r. 2. Max2Root = maximum BRdiff between r and any one its descendants. O b. 1. MaxPair = maximum BRdiff between any pair of descendants of r. O c. 1. MaxLR = maximum BRdiff between any node in left subtree of r or r itself, and any node in right subtree of r or r itself. 2. MaxL = maximum BRdiff between any two nodes in left subtree of r. 3. MaxR = maximum BRdiff between any two nodes in right subtree ofr. O d. 1. MaxLR = maximum BRdiff between any node in left subtree of r or r itself, and any node in right subtree of r or r itself. 2. MaxL = maximum BRdiff between any two nodes in left subtree ofr. 3. MaxR = maximum BRdiff between any two nodes in right subtree of r. 4. max{ 0, MaxLR, MaxL, MaxR } O e. None of the other choices
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started