Amazon Interview Question
SDE-2sCountry: United States
Interview Type: In-Person
Please suggest me solution better then this.
public class BST {
int data;
private BST lc;
private BST rc;
int sumSoFar;
BST replaceRootWithSumofGreaterNode(BST root){
if(root != null){
root.rc = replaceRootWithSumofGreaterNode(root.rc);
sumSoFar+= root.data;
root.data = sumSoFar;
root.lc = replaceRootWithSumofGreaterNode(root.lc);
}
return root;
}
BST addNode(BST root, int data){
if(root == null){
root = new BST();
root.data = data;
root.lc = root.rc = null;
return root;
}else{
if(data<root.data){
root.lc = addNode(root.lc,data);
return root;
}
else{
root.rc = addNode(root.rc,data);
return root;
}
}
}
void inorder(BST root){
if(root!=null){
inorder(root.lc);
System.out.print(root.data+"->");
inorder(root.rc);
}
}
public static void main(String[] args) {
BST b = new BST();
BST root = null;
int arr[] = {5,3,8,6,10,1,4,7,9,2};
for(int data: arr){
root = b.addNode(root, data);
}
b.inorder(root);
System.out.print("\n\n");
b.sumSoFar = 0;
root= b.replaceRootWithSumofGreaterNode(root);
b.inorder(root);
}
}
class Node {
Node leftChild;
Node rightChild;
int element;
static int sum;
Node(int element) {
this(null, null, element);
}
Node(Node leftChild, Node rightChild, int element) {
this.leftChild = leftChild;
this.rightChild = rightChild;
this.element = element;
}
}
public void reverseOrderTraversalReplaceSum(Node n) {
if(n == null)
return;
else {
reverseOrderTraversalReplaceSum(n.rightChild);
sum = sum + n.element;
n.element = sum;
reverseOrderTraversalReplaceSum(n.leftChild);
}
}
public void regenerateBinarySum()
{
// BFS uses Queue data structure
Queue<Node> queue = new LinkedList<Node>();
Queue<Node> queueToClean = new LinkedList<Node>();
queue.add(this.root);
queueToClean.add(root);
if(root.right!=null)
root.data=root.data+this.getBFSSum(root.right);
root.visited = true;
while(!queue.isEmpty()) {
Node node = (Node)queue.remove();
Node child=null;
while((child=getUnvisitedChildNode(node))!=null) {
child.visited=true;
if(child.right!=null)
child.data=child.data+this.getBFSSum(child.right);
queue.add(child);
queueToClean.add(child);
}
}
// Clear visited property of nodes
clearNodes(queueToClean);
}
private int getBFSSum(Node node)
{
// BFS uses Queue data structure
Queue<Node> queue = new LinkedList<Node>();
Queue<Node> queueToClean = new LinkedList<Node>();
queue.add(node);
queueToClean.add(node);
int sum=node.data;
node.visited = true;
while(!queue.isEmpty()) {
Node node1 = (Node)queue.remove();
Node child=null;
while((child=getUnvisitedChildNode(node1))!=null) {
child.visited=true;
sum+=child.data;
queue.add(child);
queueToClean.add(child);
}
}
// Clear visited property of nodes
clearNodes(queueToClean);
return sum;
}
I am just concentrating on the problem statement assuming the tree is already populated. Here is my private method which does the trick.
// call from any node. Inside the node class.
public void replaceSum() {
if (null == this.left && null == this.right ) {
return;
}
replace(this);
}
private void replace(Node rootNode) {
Node parent = rootNode;
Node current = null;
if (null == rootNode.left && null == rootNode.right) {
return;
}
if (null !=rootNode.getLeft()) {
current = rootNode.getLeft();
replace(current);
}
if (null !=rootNode.getRight()) {
current = rootNode.getRight();
replace(current);
}
parent.setValue(parent.getValue()+ current.value);
}
static int replace(Node node)
{
if (node == null)
return 0;
if (node.left == null)
return node.val;
else
replace(node.left);
var sum = replace(node.right);
var r = sum + node.val;
node.val = sum;
return r;
}
The problem does not state if the tree is balanced. I am also assuming there are no duplicate elements in the tree. The difficulty here is that since we are replacing the nodes values with new ones meaning that current structure of the tree may not still be valid after everything.
For example
5
/
4
/
3
would be come
5
/
9 (4+5)
/
12 (3+4+5)
So the algorithm I would use is
1) Use an in-order traversal to create sorted linked list (which is just a degenerate binary tree) O(N)
2) Recursively add the values (pretty much walk the degenerate tree to the end returning the running sum and add that to a nodes current value). At the end of everything this will still be a valid BST though a very poorly shaped one O(N)
3) Rebalance the tree using a number of left rotations O(N)
#include <stdio.h>
#include <iostream>
struct node {
struct node *left;
int data;
struct node *right;
};
void add(node **root, int data){
if(*root == NULL) {
*root = (struct node*) malloc (sizeof(struct node));
(*root)->left = (*root)->right = NULL;
(*root)->data = data;
}
}
void inorder(node *root){
if(root!=NULL) {
inorder(root->left);
printf(" %d ", root->data);
inorder(root->right);
}
}
void replaceSums(node *root, int *num) {
if(root != NULL) {
replaceSums(root->right, num);
*num += root->data;
root->data = *num;
replaceSums(root->left, num);
}
}
int main(){
node *root=NULL;
add(&(root),10);
add(&(root->left),4);
add(&(root->left->left),1);
add(&(root->left->right), 6);
add(&(root->right), 13);
add(&(root->right->left), 11);
add(&(root->right->right), 15);
printf("\n\n INORDER :: ");
inorder(root);
printf("\n\nAFTER REPLACEMENT :: ");
int a=0;
replaceSums(root,&a);
inorder(root);
return 0;
}
Output:
INORDER :: 1 4 6 10 11 13 15
AFTER REPLACEMENT :: 60 59 55 49 39 28 15
#include <iostream>
using namespace std;
// A Binary Tree Node
struct Node
{
int data;
Node *left, *right;
};
// A utility function to create a new Binary
// Tree Node
Node *newNode(int item)
{
Node *temp = new Node;
temp->data = item;
temp->left = temp->right = NULL;
return temp;
}
int ConvertSumGTET(Node *root)
{
if(root == NULL)
return 0;
ConvertSumGTET(root->left);
root->data += ConvertSumGTET(root->right);
return root->data;
}
void printTree(Node *root)
{
if(root != NULL)
{
printTree(root->left);
printTree(root->right);
cout<<"-> "<<root->data;
}
}
int main()
{
Node *root = newNode(10);
root->left = newNode(9);
root->right = newNode(15);
root->left->left = newNode(3);
root->left->left->left = newNode(2);
root->left->left->right = newNode(5);
root->right->left = newNode(12);
root->right->right = newNode(17);
root->right->left->left = newNode(11);
root->right->left->right = newNode(13);
root->right->right->left = newNode(16);
root->right->right->right = newNode(18);
printTree(root);
cout<<endl;
if(root != NULL)
root->data = ConvertSumGTET(root);
printTree(root);
return 0;
}
Do a reverse in order traversal to get the desired output.
- Nitin May 03, 2014