CareerCup

can't have a worst case log(n) time method, because if the N nodes form a single branch, you still have N operations to do...

The code below is for O(N) time O(1) space. It does a depth first traversal from right to left while keeping track of the level depth and the deepest level reached. It outputs when the deepest level increases, meaning we are at a previously unvisited level and at the right-most element of it, that is, the max.

void print_level_maxes(Node* node, int& level, int& explored_levels )
{
    if (node)
    {
        if (level>explored_levels)
        {
            std::cout << "Max of level " << level << ":  " << node->key() << std::endl;
            explored_levels++;
        }
        ++level;
        print_level_maxes(node->right,level, explored_levels);
        print_level_maxes(node->left, level, explored_levels);
        level--;
    } 
}

int main()
{
int level = 0;
int explored = -1;
print_level_maxes(tree_root, level, explored)
return 0;
}

int arr[n];
int level=0;
int *find_max_per_level(int *p,int level){
    if(p==NULL) return arr;
    arr[level++]=p->data;
    if(p->right==NULL) p=p->left;
    else p=p->right;
    find_max_per_level(p,level);
}

I could think of only O(logN)space O(N) time algorithm.

I am not sure if I got your question.
The rightmost child in a level will be the maximum element

right boundary should give the maximum at each level.

right_boundary(node)
{
if(NULL == node)
{
return;
}

/* if there is right child, then move to right child */
if(node->right != NULL)
{
right_boundary(node->right);
}
else if(node->left != NULL) /* otherwise there is only left child */
{
right_boundary(node->left);
}
/* print key for the node */
print(node->key);

return;
}

Supposed that we don't consider the space for BFS, we can do in O(n) time and O(1) for space.
we can do in the following way:
BST:

9
                                        7                             11
                           6                     8

9,7,11,6,8, for each level, the sequence should in a ascending order. Level i and Level i+1 will have a decrease, like 11->6. We can make use of this rule to print max of level i.

void printMaxByLevel ( Node * root)
{    
       if (root == NULL)
           return;
       queue<Node*> aux;
       aux.push(root);
       int max = root->key;
      int level = 0;
       while( !aux.empty( ) )
       {
             Node * current = aux.front();
             if (current < max)//Node Value  in BST right sub tree >Node Value  in BST left tree
             {
                        cout<<level<<"  "<< max << endl;
                        level++;
              }
              max = current->key;
              if (current->left != NULL)
                  aux.push (current->left);
              if (current->right != NULL)
                  aux.push (current->right);
        }
        //clean up, for the last node which is maximum node in the last level in the queue
        cout<<level<<" "<<max<<endl;
}

Advice welcome! thanks a lot.

As already told here, we can keep track of each level while doing a BFS. At each level, we can see which is the max element.

int height2(TreeNode *root) {
  if (!root) return 0;
  queue<TreeNode*> nodesQueue;
  int nodesInCurrentLevel = 1;
  int nodesInNextLevel = 0;
  int nodes = -1;
  int maxAtCurrLevel = INT_MIN;
  nodesQueue.push(root);
  while (!nodesQueue.empty()) {
    TreeNode *currNode = nodesQueue.front();
    nodesQueue.pop();
    if (currNode->data > maxAtCurrLevel) 
      maxAtCurrLevel =  currNode->data;    // If value of current node greater than current maximum of this level
    nodesInCurrentLevel--;
    if (currNode) {
      cout << currNode->data << " ";
      nodesQueue.push(currNode->left);
      nodesQueue.push(currNode->right);
      nodesInNextLevel += 2;
    }
    if (nodesInCurrentLevel == 0) {
      nodes++;
      cout<<"\n";
      nodesInCurrentLevel = nodesInNextLevel;
      nodesInNextLevel = 0;
      cout<<"Maximum element at this level: "<<maxAtCurrLevel <<endl;
     maxAtCurrLevel  = INT_MIN: //level finished
    }
  }
  return nodes;
}

We can also have an array maxVal[height] which is sized according to the height of the tree. Each entry in the array represents the maximum value at the level. Pseudocode looks like this

void findMaxLevels(tree *root, int level, int *maxVal)
{
if (!root)
return;

findMaxLevels(root->left, level+1, maxVal);

maxVal[level] = (maxVal[level] > root->data ? maxVal[level] : root->data);

findMaxLevels(root->right, level+1, maxVal);
}

We can simply print the array maxVal to get the maximum value at each level.

void maxElement(TreeNode* root)
{
      queue < pair<TreeNode*, int> > q;
      int cLevel(0) , pLevel(0);
      TreeNode* cNode;
      if (root != NULL) { q.push( make_pair(root, 1) ); cLevel = 1; max_ele = root->val ; } 
      while (!q.empty()) {
          cNode = q.top().first;
          cLevel = q.top().second; q.pop(); 
          if (cLevel != pLevel) {
                    if (pLevel) cout << max_ele << endl;
                    else max_ele = cNode->val; 
          }
          else max_ele = max(max_ele, cNode->val); 
          pLevel = cLevel;
          if (cNode->left) q.push( make_pair(cNode->left, cLevel+1) );
          if (cNode->right) q.push( make_pair(cNode->right, cLevel+1) );
      } 
      if (cLevel) cout << max_ele << endl; 
}

An attempt for log N solution (for sure in best case, but unable to prove for worst case)

Algorithm:
curNode=root
while(true) {
 print curNode value if the level is not already processed, mark this level as done
 if (curNode->left) && (curNode->right) {
   stack.push(curNode->left);
   curNode=curNode->right;
 }
 else if (curNode) curNode=(curNode->left?curNode->left:curNode->right)
 if (!curNode && !stack.isEmpty() && notAllLevelsProcessed) curNode=stack.top(); stack.pop();
}

In O(n) time and O(1) space : Morris traverse