Groupon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
This is how I did it too. I don't see anything wrong with this method. Especially since an arraylist with a very large tree would run out of memory since on reallocation it doubles the size..
void LevelOrderHelper(Node root)
{
if (root == null)
return;
int height = Height(root);
for (int i = height; i >= 1; i--)
{
LevelOrderRecursive(root, i);
Console.WriteLine();
}
}
void LevelOrderRecursive(Node root, int level)
{
if (root == null)
return;
if (level == 1)
{
Console.Write(root.data);
}
else
{
LevelOrderRecursive(root.left, level - 1);
LevelOrderRecursive(root.right, level - 1);
}
}
int Height(Node root)
{
if (root == null)
{
return 0;
}
int leftHeight = Height(root.left);
int rightHeight = Height(root.right);
if (leftHeight > rightHeight)
return leftHeight + 1;
else
return rightHeight + 1;
}
static void Main()
{
TreeProblems t = new TreeProblems();
Node root = new Node(1);
Node level1Child1 = new Node(2);
Node level1Child2 = new Node(3);
Node level2Child1 = new Node(4);
Node level2Child2 = new Node(5);
Node level2Child3 = new Node(6);
Node level2Child4 = new Node(7);
root.left = level1Child1;
root.right = level1Child2;
level1Child1.left = level2Child1;
level1Child1.right = level2Child2;
level1Child2.left = level2Child3;
level1Child2.right = level2Child4;
t.LevelOrderHelper(root);
Console.ReadLine();
}
1.Use array if you know size of tree else use arraylist
2.Keep adding right and left child until you reach at the end of tree.
3.Print elements of arraylist in revese order.
Time:O(n)
Space:O(n)
Here is a sample implementation in java:
public static void printReverseLevelOrder(TreeNode root) {
if (root == null)
return;
ArrayList<TreeNode> deque = new ArrayList<TreeNode>();
deque.add(root);
for (int i = 0; i < deque.size(); i++) {
TreeNode node = deque.get(i);
if (node.right != null) {
deque.add(node.right);
}
if (node.left != null) {
deque.add(node.left);
}
}
for (int i = deque.size() - 1; i >= 0; i--) {
System.out.print(deque.get(i).data);
}
}
I think this approach is fine, but so is the approach using a stack based on a linked-list tree implementation. If the tree is far from complete, the array-based solution would waste a lot of space and a linked-list solution would be a better choice, so which solution approach to choose would depend on the trees in question.
Analyze it...it won't take much extra space because I am using arraylist....which expands itself dynamically...
@viswa - it wont print like the way u mentioned it. The code adds the right nodes before the left ones. So the code works fine
Space taken in this approach would be O(n). You can argue that *might be* at (n-1)th node, this arraylist may expand and might take O(2n). If it is a concern then you can take a queue implemented with doubly-linled list. here space would be O(n) and you can traverse it reversely.
It is a better option than to use a queue+stack, as it will always consume O(2n) space.
"pseudocode"
print_at_depth(int n,tree * t)
{
if(t == Null) return;
if(n==0)
{
print(t->value);
return;
}
print_at_depth(n-1,t->left);
print_at_depth(n-1,t->right);
}
int max_tree_depth(tree * t)
{
if(t == Null) return 0;
return 1 + max(max_tree_depth(t->left),max_tree_depth(t->right));
}
//solution
solver(tree * t)
{
int max_d = max_tree_depth();
for(int i=max_d;i>=0;i--)
{
print_at_depth(i,t);
}
}
void levelwise_reverse(btnode* root)
{
if(root) {
queue<btnode*> q;
stack(<btnode*> stk;
q.enqueue(root);
while(!q.empty())
{
btnode* curr = q.dequeue();
stk.push(curr);
// Note we are enqueuing right node before left (diff from usual bfs level wise traversal)
if(curr->right)
q.enqueue(curr->right);
if(curr->left)
q.enqueue(curr->left);
}
while(!stk.empty())
{
cout<<stk.top();
stk.pop();
}
}
}
Using Recursion :
public void printReverseLevelOrder() {
if (this.root == null) {
return;
} else {
Queue<Node<K, V>> nodeQueue1 = new LinkedList<Node<K, V>>();
nodeQueue1.add(root);
System.out.println(printReverseLevelOrderHelper(nodeQueue1));
}
}
public String printReverseLevelOrderHelper(Queue<Node<K, V>> nodeQueue1){
StringBuilder output = new StringBuilder();
Queue<Node<K, V>> nodeQueue2 = new LinkedList<Node<K, V>>();
while (!nodeQueue1.isEmpty()) {
Node<K, V> curNode = nodeQueue1.remove();
output.append(curNode.value + " ");
if (curNode.leftchild != null) {
nodeQueue2.add(curNode.leftchild);
}
if (curNode.rightchild != null) {
nodeQueue2.add(curNode.rightchild);
}
}
if(!nodeQueue2.isEmpty()){
System.out.println(printReverseLevelOrderHelper(nodeQueue2));
}
return output.toString();
}
Use a queue for level order traversal and a stack to print the data in reverse order.
- Anonymous December 03, 2012