CareerCup

Can be done through recursion. Below is the sample code. Haven't compiled it, so pardon if there are any syntax error.

class Treenode {
  private:
     int data_;
     Treenode *left_;
     Treenode *right_;
  public:
     int get_data(void) {return data_;}
     Treenode* get_left(void) {return left_;}
     Treenode* get_right(void) {return right_;}
};

int main() {
  vector<list*> vector_of_lists;
  Treenode *root; //Input the tree root node here
  /*Assuming the hieght of the tree is h*/
  for(int i=0; i<(2*h+1); i++) {
    vector_of_lists[i] = new list<int>;
  }
  print_vertical_list(root, h);
  for(int i=0; i<(2*h+1); i++) {
    list<int>::iterator it;
    for(it = vector_of_lists[i]->begin(); it != vector_of_lists[i]->end(); it++) {
      cout << *it << " ";
    }
    cout << endl;
  }
}


void 
print_vertical_list(TreeNode *root, int position) {
  if(root != NULL) {
    vector_of_lists[position]->push_back(root->get_data());
    print_vertical_list(root->get_left(), postion-1);
    print_vertical_list(root->get_right(), position+1);
  }
}

Time complexity is O(n) and Space complexity is O(n)

Here is what I thought

Let say he starts from root and index = 0. Reduce index by 1 if he goes to left and increase index by 1 when goes to right. and enter into a hash with index as the key.
Now print the hash taking the min index and traversing to the max index.

Was this a question from a company?

Start with level = 0 , for every left traverst decrese the level by -1 and for every right traversal increast the level by +1, taking level as the key insert element into the hasttable