Amazon Coding Questions

// C++ Program to print Bottom View of Binary Tree
#include<bits/stdc++.h>
using namespace std;

// Tree node class
struct Node
{
	int data; //data of the node
	int hd; //horizontal distance of the node
	Node *left, *right; //left and right references

	// Constructor of tree node
	Node(int key)
	{
		data = key;
		hd = INT_MAX;
		left = right = NULL;
	}
};

// Method that prints the bottom view.
void bottomView(Node *root)
{
	if (root == NULL)
		return;

	// Initialize a variable 'hd' with 0
	// for the root element.
	int hd = 0;

	// TreeMap which stores key value pair
	// sorted on key value
	map m;

	// Queue to store tree nodes in level
	// order traversal
	queue q;

	// Assign initialized horizontal distance
	// value to root node and add it to the queue.
	root->hd = hd;
	q.push(root); // In STL, push() is used enqueue an item

	// Loop until the queue is empty (standard
	// level order loop)
	while (!q.empty())
	{
		Node *temp = q.front();
		q.pop(); // In STL, pop() is used dequeue an item

		// Extract the horizontal distance value
		// from the dequeued tree node.
		hd = temp->hd;

		// Put the dequeued tree node to TreeMap
		// having key as horizontal distance. Every
		// time we find a node having same horizontal
		// distance we need to replace the data in
		// the map.
		m[hd] = temp->data;

		// If the dequeued node has a left child, add
		// it to the queue with a horizontal distance hd-1.
		if (temp->left != NULL)
		{
			temp->left->hd = hd-1;
			q.push(temp->left);
		}

		// If the dequeued node has a right child, add
		// it to the queue with a horizontal distance
		// hd+1.
		if (temp->right != NULL)
		{
			temp->right->hd = hd+1;
			q.push(temp->right);
		}
	}

	// Traverse the map elements using the iterator.
	for (auto i = m.begin(); i != m.end(); ++i)
		cout << i->second << " ";
}

// Driver Code
int main()
{
	Node *root = new Node(20);
	root->left = new Node(8);
	root->right = new Node(22);
	root->left->left = new Node(5);
	root->left->right = new Node(3);
	root->right->left = new Node(4);
	root->right->right = new Node(25);
	root->left->right->left = new Node(10);
	root->left->right->right = new Node(14);
	cout << "Bottom view of the given binary tree :\n";
	bottomView(root);
	return 0;
}

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

// Tree node structure
typedef struct Node
{
  int data;			// Data of the node
  int hd;			// Horizontal distance of the node
  struct Node *left, *right;	// Left and right references
} Node;

// Constructor of tree node
Node *createNode (int key)
{
  Node *newNode = (Node *) malloc (sizeof (Node));
  newNode->data = key;
  newNode->hd = INT_MAX;
  newNode->left = newNode->right = NULL;
  return newNode;
}

// Linked list to store tree nodes in level order traversal
typedef struct QueueNode
{
  Node *node;
  struct QueueNode *next;
} QueueNode;

// Balanced Binary Search Tree to store key value pair
typedef struct MapNode
{
  int key;
  int value;
  struct MapNode *left;
  struct MapNode *right;
} MapNode;

// Create a new MapNode and initialize its values
MapNode *createMapNode (int key, int value)
{
  MapNode *newMapNode = (MapNode *) malloc (sizeof (MapNode));
  newMapNode->key = key;
  newMapNode->value = value;
  newMapNode->left = newMapNode->right = NULL;
  return newMapNode;
}

// Insert a new MapNode into the balanced BST
MapNode *insertMapNode (MapNode * node, int key, int value)
{
  if (node == NULL)
    return createMapNode (key, value);

  if (key < node->key)
    node->left = insertMapNode (node->left, key, value);
  else if (key > node->key)
    node->right = insertMapNode (node->right, key, value);
  else
    {
      // Update the value for nodes with the same horizontal distance
      node->value = value;
    }

  return node;
}

// Enqueue a tree node to the queue
void enqueue (QueueNode ** front, QueueNode ** rear, Node * node)
{
  QueueNode *newQueueNode = (QueueNode *) malloc (sizeof (QueueNode));
  newQueueNode->node = node;
  newQueueNode->next = NULL;

  if (*rear == NULL)
    {
      *front = *rear = newQueueNode;
      return;
    }

  (*rear)->next = newQueueNode;
  *rear = newQueueNode;
}

// Dequeue a tree node from the queue
Node * dequeue (QueueNode ** front, QueueNode ** rear)
{
  if (*front == NULL)
    return NULL;

  QueueNode *temp = *front;
  Node *node = temp->node;
  *front = (*front)->next;

  if (*front == NULL)
    *rear = NULL;

  free (temp);
  return node;
}

// Method that prints the bottom view.
void bottomView (Node * root)
{
  if (root == NULL)
    return;

  // Initialize a variable 'hd' with 0 for the root element.
  int hd = 0;

  QueueNode *front = NULL;
  QueueNode *rear = NULL;

  MapNode *rootMap = NULL;

  // Assign initialized horizontal distance value to root node and add it to the queue.
  root->hd = hd;
  enqueue (&front, &rear, root);

  // Loop until the queue is empty (standard level order loop)
  while (front != NULL)
    {
      Node *temp = dequeue (&front, &rear);

      // Extract the horizontal distance value from the dequeued tree node.
      hd = temp->hd;

      // Put the dequeued tree node to the balanced BST having key as horizontal distance.
      // Every time we find a node having the same horizontal distance, we need to replace the data in the BST.
      rootMap = insertMapNode (rootMap, hd, temp->data);

      // If the dequeued node has a left child, add it to the queue with a horizontal distance hd-1.
      if (temp->left != NULL)
	{
	  temp->left->hd = hd - 1;
	  enqueue (&front, &rear, temp->left);
	}

      // If the dequeued node has a right child, add it to the queue with a horizontal distance hd+1.
      if (temp->right != NULL)
	{
	  temp->right->hd = hd + 1;
	  enqueue (&front, &rear, temp->right);
	}
    }

  // Traverse the map elements in order and print the values
  MapNode *currentNode = rootMap;
  while (currentNode != NULL)
    {
      printf ("%d ", currentNode->value);
      currentNode = currentNode->right;
    }
}

// Driver Code
int main ()
{
  Node *root = createNode (20);
  root->left = createNode (8);
  root->right = createNode (22);
  root->left->left = createNode (5);
  root->left->right = createNode (3);
  root->right->left = createNode (4);
  root->right->right = createNode (25);
  root->left->right->left = createNode (10);
  root->left->right->right = createNode (14);
  printf ("Bottom view of the given binary tree:\n");
  bottomView (root);
  return 0;
}