Goldman Sachs Interview Question
Software Engineer / Developers#include <stdio.h>
#include <stdlib.h>
/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
};
/*Function protoypes*/
void printGivenLevel(struct node* root, int level);
int height(struct node* node);
struct node* newNode(int data);
/* Function to print level order traversal a tree*/
void printLevelOrder(struct node* root)
{
int h = height(root);
int i;
for(i=h; i>=1; i--)
printGivenLevel(root, i);
}
/* Print nodes at a given level */
void printGivenLevel(struct node* root, int level)
{
if(root == NULL)
return;
if(level == 1)
printf("%d ", root->data);
else if (level > 1)
{
printGivenLevel(root->left, level-1);
printGivenLevel(root->right, level-1);
}
}
/* Compute the "height" of a tree -- the number of
nodes along the longest path from the root node
down to the farthest leaf node.*/
int height(struct node* node)
{
if (node==NULL)
return 0;
else
{
/* compute the height of each subtree */
int lheight = height(node->left);
int rheight = height(node->right);
/* use the larger one */
if (lheight > rheight)
return(lheight+1);
else return(rheight+1);
}
}
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
/* Driver program to test above functions*/
int main()
{
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
printf("Level Order traversal of binary tree is \n");
printLevelOrder(root);
getchar();
return 0;
}
#include <stdio.h>
#include <stdlib.h>
/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
};
/*Function protoypes*/
void printGivenLevel(struct node* root, int level);
int height(struct node* node);
struct node* newNode(int data);
/* Function to print level order traversal a tree*/
void printLevelOrder(struct node* root)
{
int h = height(root);
int i;
for(i=h; i>=1; i--)
printGivenLevel(root, i);
}
/* Print nodes at a given level */
void printGivenLevel(struct node* root, int level)
{
if(root == NULL)
return;
if(level == 1)
printf("%d ", root->data);
else if (level > 1)
{
printGivenLevel(root->left, level-1);
printGivenLevel(root->right, level-1);
}
}
/* Compute the "height" of a tree -- the number of
nodes along the longest path from the root node
down to the farthest leaf node.*/
int height(struct node* node)
{
if (node==NULL)
return 0;
else
{
/* compute the height of each subtree */
int lheight = height(node->left);
int rheight = height(node->right);
/* use the larger one */
if (lheight > rheight)
return(lheight+1);
else return(rheight+1);
}
}
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
/* Driver program to test above functions*/
int main()
{
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
printf("Level Order traversal of binary tree is \n");
printLevelOrder(root);
getchar();
return 0;
}
#include <queue>
#include <stack>
#include <iostream>
using namespace std;
void traverseLevelOrder(btree *p)
{
if(p == NULL)
return;
queue<btree*> pNodes;
stack<btree*> allNodes;
pNodes.push(p);
int count;
btree* node;
/* add all level nodes in stack */
while(!pNodes.empty())
{
count = pNodes.size();
for(int i = 1; i <= count; i++)
{
node = pNodes.front();
allNodes.push(node);
if(node->left != NULL)
pNodes.push(node->left);
if(node->right != NULL)
pNodes.push(node->right);
pNodes.pop();
}
}
while(!allNodes.empty())
{
cout << allNodes.top()->key << "\t";
allNodes.pop();
}
}
public static string TraverseBreadthFirstDepthReverse<T>(this BinaryNode<T> root)
{
var queue = new Queue<BinaryNode<T>>();
var stack = new Stack<BinaryNode<T>>();
var sb = new StringBuilder();
queue.Enqueue(root);
while (queue.Count > 0)
{
var node = queue.Dequeue();
stack.Push(node);
if (node.RightNode != null)
queue.Enqueue(node.RightNode);
if (node.LeftNode != null)
queue.Enqueue(node.LeftNode);
}
while (stack.Count > 0)
{
var node = stack.Pop();
sb.Append(node.Value);
}
return sb.ToString();
}
package goldmansach;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import main.java.algorithms.binarytree.BinaryTree;
import main.java.algorithms.binarytree.Node;
public class LevelOrderReverse {
public void reverseUtil(Queue<Node> mainQueue) {
Queue<Node> q= new LinkedList<>();
int k = mainQueue.size();
while(k>0){
Node n = mainQueue.poll();
q.add(n);
if(n.left!=null)mainQueue.add(n.left);
if(n.right!=null)mainQueue.add(n.right);
k--;
}
if(mainQueue.size() >0)reverseUtil(mainQueue);
while(!q.isEmpty()) {
System.out.print(q.poll().root+" ");
}
System.out.println();
}
public void levelOrderReversal(BinaryTree tree){
Queue<Node> q= new LinkedList<>();
q.add(tree.root);
reverseUtil(q);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
LevelOrderReverse l = new LevelOrderReverse();
BinaryTree tree= new BinaryTree();
tree.root = new Node(1);
tree.root.left =new Node(2);
tree.root.right =new Node(3);
tree.root.left.left =new Node(4);
tree.root.left.right =new Node(5);
tree.root.right.left =new Node(6);
tree.root.right.right =new Node(7);
l.levelOrderReversal(tree);
}
}
package goldmansach;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import main.java.algorithms.binarytree.BinaryTree;
import main.java.algorithms.binarytree.Node;
public class LevelOrderReverse {
public void reverseUtil(Queue<Node> mainQueue) {
Queue<Node> q= new LinkedList<>();
int k = mainQueue.size();
while(k>0){
Node n = mainQueue.poll();
q.add(n);
if(n.left!=null)mainQueue.add(n.left);
if(n.right!=null)mainQueue.add(n.right);
k--;
}
if(mainQueue.size() >0)reverseUtil(mainQueue);
while(!q.isEmpty()) {
System.out.print(q.poll().root+" ");
}
System.out.println();
}
public void levelOrderReversal(BinaryTree tree){
Queue<Node> q= new LinkedList<>();
q.add(tree.root);
reverseUtil(q);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
LevelOrderReverse l = new LevelOrderReverse();
BinaryTree tree= new BinaryTree();
tree.root = new Node(1);
tree.root.left =new Node(2);
tree.root.right =new Node(3);
tree.root.left.left =new Node(4);
tree.root.left.right =new Node(5);
tree.root.right.left =new Node(6);
tree.root.right.right =new Node(7);
l.levelOrderReversal(tree);
}
}
package goldmansach;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import main.java.algorithms.binarytree.BinaryTree;
import main.java.algorithms.binarytree.Node;
public class LevelOrderReverse {
public void reverseUtil(Queue<Node> mainQueue) {
Queue<Node> q= new LinkedList<>();
int k = mainQueue.size();
while(k>0){
Node n = mainQueue.poll();
q.add(n);
if(n.left!=null)mainQueue.add(n.left);
if(n.right!=null)mainQueue.add(n.right);
k--;
}
if(mainQueue.size() >0)reverseUtil(mainQueue);
while(!q.isEmpty()) {
System.out.print(q.poll().root+" ");
}
System.out.println();
}
public void levelOrderReversal(BinaryTree tree){
Queue<Node> q= new LinkedList<>();
q.add(tree.root);
reverseUtil(q);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
LevelOrderReverse l = new LevelOrderReverse();
BinaryTree tree= new BinaryTree();
tree.root = new Node(1);
tree.root.left =new Node(2);
tree.root.right =new Node(3);
tree.root.left.left =new Node(4);
tree.root.left.right =new Node(5);
tree.root.right.left =new Node(6);
tree.root.right.right =new Node(7);
l.levelOrderReversal(tree);
}
}
Postorder traversal will also work in this case. It will first print the left child then right child and then parent.
Postorder can't work. They want it in level order. e.g. if you do postorder, the immediate left child of root will get printed before the leaves of the right child. We don't want that, do we?
exactly, you are right..its very true that post order cant work in this case because the roots at the same level gets printed before the right child of these roots.
exactly, you are right..its very true that post order cant work in this case because the roots at the same level gets printed before the right child of these roots.
using another Stack to save the immediate value, then print the Stack
- Anonymous March 06, 2010