Amazon Interview Question
Software Engineer / DevelopersCountry: Canada
Interview Type: Phone Interview
# In Python a simple way to represent a binary
# tree is as a tuple: (left_tree, val, right_tree)
def create_tree(lst):
def _maketree(low, high):
# Making a balanced tree is simply a matter
# of taking the middle value as the root
# and recursively building the subtrees
# on the left and right.
if low > high:
return None
if low == high:
return (None, lst[low], None)
mid = (low + high) / 2
val = lst[mid]
left = _maketree(low, mid - 1)
right = _maketree(mid + 1, high)
return (left, val, right)
return _maketree(0, len(lst) - 1)
def traverse(tree):
if tree is None:
return
left, val, right = tree
traverse(left)
print val
traverse(right)
def tree_height(tree):
if tree is None:
return 0
left, val, right = tree
lh = tree_height(left)
rh = tree_height(right)
return max([lh, rh]) + 1
lst = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
tree = create_tree(lst)
print tree
assert 4 == tree_height(tree)
traverse(tree)
BinaryTree* sortedArrayToBST(int arr[], int start, int end) {
if (start > end) return NULL;
int mid = (start + start) / 2;
BinaryTree *node = new BinaryTree(arr[mid]);
node->left = sortedArrayToBST(arr, start, mid-1);
node->right = sortedArrayToBST(arr, mid+1, end);
return node;
}
BinaryTree* sortedArrayToBST(int arr[], int n) {
return sortedArrayToBST(arr, 0, n-1);
}
#include <stdio.h>
#include <stdlib.h>
struct node
{
int value;
struct node* left;
struct node* right;
};
struct node* constructBST(int*,int,int);
void printTree(struct node*);
void main()
{
int array[10] = {1,2,3,4,5,6,7,8,9,10};
int start = 0;
int end = 9;
struct node *head;
head = constructBST(array, start, end);
printTree(head);
return;
}
struct node* constructBST(int *array, int start, int end)
{
int size = end - start + 1;
if(size == 1)
{
struct node *nd;
nd = (struct node*)malloc(sizeof(struct node));
nd->value = array[start];
nd->left = NULL;
nd->right = NULL;
return nd;
}else if(size == 0)
{
return NULL;
}else{
int median = (start + end)/2;
struct node *nd;
nd = (struct node*)malloc(sizeof(struct node));
nd->value = array[median];
nd->left = constructBST(array, start, median-1);
nd->right = constructBST(array, median+1, end);
return nd;
}
}
void printTree(struct node *head)
{
struct node *curr = head;
if(curr == NULL)
return;
printTree(curr->left);
printf("%d->", curr->value);
printTree(curr->right);
}
TreeNode* CreateTree(TreeNode *root, int *arr, int l, int r)
{
if(l == r + 1 || r == l -1)
return NULL;
else
{
int mid = (l + r) / 2;
root = new TreeNode();
root->data = arr[mid];
root->left = CreateTree(root, arr, l, mid-1);
root->right = CreateTree(root, arr, mid+1, r);
}
return root;
}
Recursive version.
- Anonymous February 19, 2013