1

I am trying to solve an exercise where you are given a perfect ternary tree in which each node contains an integer. We want to calculate how many internal nodes meet these specifications:

  1. The number of the node is larger than all its children
  2. It's largest child is the middle one

For example in the following tree there are only 3 nodes who meet these specifications Example

Design and analyze a divide and conquer algorithm which calculates the number of nodes who meet the specifications. This algorithm should be of O(n), where n is the number of leaves and n is a power of 3. Don't take into consideration the data structure of the tree, just explain a algorithm

So i tried designing this algorithm: Algorithm I am new to algorithm design and i do not know of what time complexity is what i did or even if it is a divide and conquer algorithm. Please if you know how to help me computing the time complexity of this or checking if it actually is a divide and conquer solution please tell me. Also if you have an idea that is better than mine please help out. Thanks

Martijn Pieters
  • 1,048,767
  • 296
  • 4,058
  • 3,343
Chris Costa
  • 653
  • 4
  • 15

1 Answers1

2

First, almost every recursion can regarded as divide and conquer because you split your problem to sub problems.

Second, notice that you visit each node of the tree at most once, hence the running time is indeed O(n) as you wished

  • I just noticed that you defined n as the number of leaves, and not as the number of nodes, but the analyze remains valid because for a tree in height h number of nodes is 1+3+..+3^h-1 = O(3^h) and in the h level there are 3^h leaves exactly. So the algorithm is indeed runs in ~O(3n)=O(n) time

Last point, I think what you did is actually good! but in practical, I think that writing recursion in this cases is mostly by "branches" and not by levels, which means that you advance deep before you advance wide. to make this clearer, what I mean, is that the final code will look like:

def countSpeacialNodes (Node t):
if t doesnt have children: return 0
if t is bigger than its children AND t's biggest child is the middle:
return 1+CSN(t.left)+CSN(t.middle)+CSN(t.right)
else return CSN(t.left)+CSN(t.middle)+CSN(t.right)

so to summarist, you can notice that advancing here is to the deep of the tree before to the "wide" of the tree, and also that it is not necessary to mark nodes

Hope it helps a little

e.ad
  • 380
  • 2
  • 10
  • 1
    Sure, no problem. By 'any given tree' you mean any ternary tree? or complete (each node has 3 children or 0 children)? Asking coz the first case require a little modification of the code. Anyway, the induction here will be on the height of the tree: first show that for a given tree of height 0 it is working (Sure it will! it will exit the code after the first line and will return 0!) and then assume for height 'h-1' the code is working. and the last part is to show it for a tree of height h which is easy because the 'return' lines already separate to cases for you. tell me more help is needed – e.ad Feb 09 '21 at 17:56