Answered step by step
Verified Expert Solution
Link Copied!

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.

image text in transcribed

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

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Database Driven Web Sites

Authors: Joline Morrison, Mike Morrison

2nd Edition

? 061906448X, 978-0619064488

More Books

Students also viewed these Databases questions

Question

Why is the System Build Process an iterative process?

Answered: 1 week ago