Google Interview Question Software Engineer / Developers
Country: United States
Do we need multi threads here?
I have the same logic as you. But I think I am not able to implement with single thread. Plz write code if possible
we don't actually, we apply while loop here, and store node into stack(not just values), and in each loop we do above check, (mean updating the stacks),
I will write single threaded code of it on this thursday, as i have some quizzes in this week.
Someone please provide java code or explanation for this BST (after each iteration, with contents of S1, S2) -
5
3 8
2 4 6 9
2.1 3.1
I want to search for sum=5.2
let s1 and s2 are two stack
initially s1 contain : [3,2]
and s2 contain : [5,8,9]
we sum 2 and 9 and compare then with 5.2 and 11 is bigger then 5.2 so we look for left child of 9 which is not there, so we pop 9 from s2
now stacks contains
s1 : [3,2]
s2 : [5,8]
again 2+8 > 5.2 so we pop 8 and push 6
now stacks contain :
s1 : [3,2]
s2 : [5,6]
now again 2+6 > 5.2, we pop 6 from it
now stacks contain :
s1 : [3,2]
s2 : [5]
again 2+5 > 5.2 so we pop 5 from it and push [3,4] into it
now stacks are :
s1 : [3,2]
s2 : [3,4]
again 2+4 > 5.3 so we pop 4 and push 3.1 into it
now stacks contains :
s1 : [3,2];
s2 : [3,3.1]
here 2+3.1 < 5.2 so we pop 2 from s1 and push 2.1 into it
now stack contains :
s1 : [3,2.1]
s2 : [3,3.1]
now 2.1 + 3.1 = 5.2 we get our answer, we print 3.1 and 2.1, if there is a possibility of having multiple pairs, then we won't stop here we go upto the condition that element of s1 is smaller then element of s2.
Your solution didn't seem to work when the left tree only contains one node.
e.g. create the tree with 7, 20, 2, 12, 17, 22 with target 37
s1 = [2]
s2 = [7,20,22]
2 + 22 < 37 so you pop 2 .. now what? it has no right subtree - you can't check the left/right elements as the condition of your loop.
I forgot one thing to write here which is that root node is included in both the stacks, as i am checking the condition which is that stack1's element should be smaller then stack2's element, so this will not create any problem, but it solve problems like yours, thanks for that,
here is the execution :
s1 = [7,2]
s2 = [7,20,22]
2+22 < 37
s1 = [7]
s2 = [7,20,22]
7+22 < 37
s1 = [20,12]
s2 = [7,20,22]
12+22 < 37
s1 = [20 17]
s2 = [7,20,22]
17+22 > 37
s1 = [20,17]
s2 = [7,20]
17+20 = 37;
thanks - this code seems to work then:
public void printTwoNodeValueEqualToX(Integer value) {
Stack<BinaryNode> leftStack = new Stack<BinaryNode>();
Stack<BinaryNode> rightStack = new Stack<BinaryNode>();
BinaryNode scan = root;
while (scan != null) {
leftStack.add(scan);
scan = scan.left;
}
scan = root;
while (scan != null) {
rightStack.add(scan);
scan = scan.right;
}
do {
if (leftStack.peek().item + rightStack.peek().item > value) {
BinaryNode rightElem = rightStack.pop();
if (rightElem.left != null) {
scan = rightElem.left;
while (scan != null) {
rightStack.add(scan);
scan = scan.right;
}
}
} else if (leftStack.peek().item + rightStack.peek().item < value) {
BinaryNode leftElem = leftStack.pop();
if (leftElem.right != null) {
scan = leftElem.right;
while (scan != null) {
leftStack.add(scan);
scan = scan.left;
}
}
} else {
System.out.println(leftStack.peek().item + ", "
+ rightStack.peek().item);
return;
}
} while (leftStack.peek().item < rightStack.peek().item);
System.out.println("not found");
}
In ur code
if(A[1st_index] + A[2nd_index] < x)
it this is true then there will be no two values with the required sum x.....then why are u subtracting 2nd_index--......
To readers,
FOR THE OBSERVATION PART (above):
===============================
Array example is considered to be sorted in non-increasing fashion.
"
observation : if we are given a sorted array instead of a BST and the same question was asked then so solve this problem in O(n)+O(1) complexity, we keep two indexes one at start and 2nd one at end, and apply following algo.
if(A[1st_index] + A[2nd_index] < x)
2nd_index--;
else if (A[1st_index] + A[2nd_index] > x)
1st_index++;
else
print 1st_index,2nd_index;
do this until 2nd_index > 1st_index
"
I think the code 'printTwoNodeValueEqualToX()' will fail to the following test case:
{1, 2, 2, 10}, sum = 4
I think it should not use 'while (leftStack.peek().item < rightStack.peek().item);',
because in the above example, the answer is {2, 2}, with the same value in the pair.
I think it should use 'while (leftStack.peek() != rightStack.peek());'.
BTW, the follwoing is my Java implementation together with some simple tests,
I'd appreciate any bug if you found:
import java.util.*;
class Node
{
public Node lChild = null;
public Node rChild = null;
public int data;
public Node(int d) {data = d;}
}
class G215
{
public static Node[] findTowNodesSumTo(Node root, int sum)
{
Node n1 = root;
Node n2 = root;
Stack<Node> stack1 = new Stack<Node>();
Stack<Node> stack2 = new Stack<Node>();
while ((null != n1 || !stack1.isEmpty()) && (null != n2 || !stack2.isEmpty()))
{
if (null != n1) {stack1.push(n1); n1 = n1.lChild; continue;}
if (null != n2) {stack2.push(n2); n2 = n2.rChild; continue;}
if (stack1.peek() == stack2.peek()) {return null;}
int s = stack1.peek().data + stack2.peek().data;
if (s == sum)
{
Node[] result = new Node[2];
result[0] = stack1.peek();
result[1] = stack2.peek();
return result;
}
if (s > sum)
{
n2 = stack2.pop();
n2 = n2.lChild;
}
else
{
n1 = stack1.pop();
n1 = n1.rChild;
}
}
return null;
}
public static void main(String[] args)
{
// First test case
int[] array1 = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512};
Node tree1 = createTree(array1);
Node[] result1 = findTowNodesSumTo(tree1, 80);
System.out.println("result1:");
if (null != result1) for (Node n : result1) {System.out.println("" + n.data);}
// Second test case
int[] array2 = {1, 4, 9, 16, 25, 36, 49, 64, 81, 100};
Node tree2 = createTree(array2);
Node[] result2 = findTowNodesSumTo(tree2, 72);
System.out.println("result2:");
if (null != result2) for (Node n : result2) {System.out.println("" + n.data);}
}
public static Node createTree(int[] array)
{
return createTree(array, 0, array.length - 1);
}
private static Node createTree(int[] array, int begin, int end)
{
if (begin > end) {return null;}
if (begin == end) {return new Node(array[begin]);}
int size = end - begin + 1;
int lSize = (size - 1) / 2;
Node n = new Node(array[begin + lSize]);
n.lChild = createTree(array, begin, begin + lSize - 1);
n.rChild = createTree(array, begin + lSize + 1, end);
return n;
}
}
Isnt it like we are comparing the inorder and reverse inorder elements? This solution is pretty good.
@Alva0930 what is the running time and space for your solution? Could you please tell us?
Are your comparison operators flipped in the original post? I get the logic, based on later comment examples. However, when I look at the original post, it seems like I want to be doing the opposite of what each 'if statement' suggests to do.
Since the above code implementing @sonesh's idea is not clear enough, I submit the following simple implementation in Java:
public void findNodes(Node root, int sum) {
Stack<Node> left = new Stack<Node>();
Stack<Node> right = new Stack<Node>();
Node x = root;
while (x != null) {
left.push(x);
x = x.left;
}
x = root;
while (x != null) {
right.push(x);
x = x.right;
}
while (!left.isEmpty() && !right.isEmpty()) {
Node lNode = left.peek();
Node rNode = right.peek();
int s = lNode.key + rNode.key;
if (s < sum) {
left.pop();
if (lNode.right != null) {
left.push(lNode.right);
}
} else if (s > sum) {
right.pop();
if (rNode.left != null) {
right.push(rNode.left);
}
} else {
System.out.println(lNode.key + " " + rNode.key);
break;
}
}
}
My fifty cents (full C++ solution, O(h) space complexity, O(n log n) time complexity) :
#include <iostream>
using namespace std;
// We need to define the structurs for BST and stacks (using linked-list)
class BSTNode {
public:
int value;
BSTNode *left;
BSTNode *right;
BSTNode(int value, BSTNode *left=NULL, BSTNode *right=NULL) {
this->value = value;
this->left = left;
this->right = right;
}
int contains(int value, BSTNode *exclude=NULL) {
if (value < this->value)
return (this->left != NULL && this->left->contains(value, exclude));
else if (value > this->value)
return (this->right != NULL && this->right->contains(value, exclude));
else
return (this == exclude) ? 0 : 1;
}
};
class LLNode {
public:
BSTNode *tree;
LLNode *next;
LLNode(BSTNode *tree, LLNode *next) {
this->tree = tree;
this->next = next;
}
};
class Stack {
public:
LLNode *head;
Stack() {
this->head = NULL;
}
~Stack() {
LLNode *oldHead;
while (this->head != NULL) {
oldHead = this->head;
this->head = oldHead->next;
delete oldHead;
}
}
void push(BSTNode *tree) {
this->head = new LLNode(tree, this->head);
}
BSTNode *pop() {
LLNode *oldHead = this->head;
if (oldHead == NULL)
return NULL;
BSTNode *ret = oldHead->tree;
this->head = oldHead->next;
delete oldHead;
return ret;
}
};
/*
We performe a depth-first search on the BST using a stack which size won't
grow over O(height of the tree).
For each node we find, we check in logarithmic time whether the complement is
in the tree (taking care of excluding this node).
*/
int findNodesWithSum(BSTNode *root, int sum) {
Stack stack;
stack.push(root);
BSTNode *curTree;
while ((curTree = stack.pop()) != NULL) {
if (root->contains(sum - curTree->value, curTree)) {
cout << curTree->value << "+" << (sum - curTree->value) << endl;
return 1;
}
if (curTree->right != NULL)
stack.push(curTree->right);
if (curTree->left != NULL)
stack.push(curTree->left);
}
return 0;
}
int main(int argc, char* argv[]) {
/*
13
5 15
3 8 14 17
*/
BSTNode *root = new BSTNode(13,
new BSTNode(5,
new BSTNode(3),
new BSTNode(8)),
new BSTNode(15,
new BSTNode(14),
new BSTNode(17))
);
findNodesWithSum(root, 10); // Not found
findNodesWithSum(root, 9); // 5+8
findNodesWithSum(root, 13); // Not found
findNodesWithSum(root, 20); // 5+15
return 0;
}
#include<conio.h>
#include<stdlib.h>
#include<stdio.h>
struct graph
{
int value;
struct graph *left;
struct graph *right;
}*root;
struct graph *creategraph(int k)
{
struct graph *temp=malloc(sizeof(struct graph));
temp->value=k;
temp->left=NULL;
temp->right=NULL;
return temp;
}
int Search(struct graph *root,struct graph *m, int diff)
{
struct graph *r=root;
while(r!=NULL)
{
if(r->value==diff && r!=m)
{
printf("First Node :%d\n",r->value);
return 1;
}
if(r->value<diff)
r=r->right;
else
r=r->left;
}
}
void Find2NodeSumisX(struct graph *k,int sum)
{
if(k==NULL)
return;
int i=0;
i=Search(root,k,sum-k->value);
if(i==1)
{
printf("Second Node Value: %d\n Found!!",k->value);
exit(0); // if You want to print all such combination of two node which give a sum of X remove exit(0)
}
if(k->value>=sum)
Find2NodeSumisX(k->left,sum); // if sum<=root->value the both required node must be in left subtree
else
{
Find2NodeSumisX(k->left,sum);
Find2NodeSumisX(k->right,sum);
}
}
int main()
{
root=creategraph(11);
root->left=creategraph(4);
root->right=creategraph(15);
root->left->left=creategraph(3);
root->left->right=creategraph(8);
root->left->left->left=creategraph(7);
root->left->left->left->left=creategraph(1);
root->right->left=creategraph(10);
root->right->right=creategraph(16);
root->right->right->right=creategraph(14);
root->right->left->left=creategraph(5);
root->right->right->right->right=creategraph(2);
int X=31;
Find2NodeSumisX(root,X);
}
Here is solution as per space complexity, but high time complexity. If any one get soln with less complexity will be better.
BOOL TwoNodeSum(NODE *Root, int x, NODE **N1, NODE **N2)
{
NODE *Mn = NULL, *Mx = NULL, *List[HIGHT], *TN = NULl, *TN2 = NULl;
int sum = 0, i = 0;
Mn = min(Root);
Mx = max(Root);
while(Mn->info < Mx->info){
sum = Mn->info + Mx->info;
if(sum == x){
*N1 = Mn;
*N2 = Mx;
return TRUE;
}else if(sum > x){//Get Predecessor of Max Node i.e. of Mx
TN = Root;
i = 0;
while(Mx->info != TN->info){
List[i++] = TN;
if(Mx->info < TN->info) TN = TN->Left;
else TN = TN->Right;
}
PN = List[--i];
if(Mx->Left != NULL){
Mx = max(Mx->Left);
}else if(PN != NULL){
if(PN->Right == Mx) Mx = PN;
else{
TN2 = List[--i];
SWAP(TN2, PN);
while(PN->Left == TN2){
TN2 = List[--i];
SWAP(TN2, PN);
}
Mx = PN;
}
}else{//Get Sucessor of Min Node i.e. of Mn
TN = Root;
i = 0;
while(Mn->info != TN->info){
List[i++] = TN;
if(Mx->info < TN->info) TN = TN->Left;
else TN = TN->Right;
}
PN = List[--i];
if(Mn->Right != NULL){
Mn = min(Mn->Right);
}else if(PN != NULL){
if(PN->Left == Mn) Mn = PN;
else{
TN2 = List[--i];
SWAP(TN2, PN);
while(PN->Right == TN2){
TN2 = List[--i];
SWAP(TN2, PN);
}
Mn = PN;
}
}
}//while
}
Logic :
How do you find two values whose sum equal to X in a sorted array.
- keep one pointer at start and another at end of an array and move your pointers according as per sum.
Used same logic, however instead of array, think how to do it in BST.
public class BSTAndValueXTwoNode {
public int index = 0;
public void printTwoNodeValueEqualToX(Node root,int x)
{
int numberOfNodes = numberOfNodes(root);
int low = 0;
int high = numberOfNodes-1;
int lowNodeValue;
int highNodeValue;
while(low<high)
{
lowNodeValue = findValueAtIndex(root, low);
highNodeValue = findValueAtIndex(root, high);
if(lowNodeValue + highNodeValue == x)
{
System.out.println(lowNodeValue + " " + highNodeValue);
break;
}
else if(lowNodeValue + highNodeValue < x)
{
low++;
}
else
{
high--;
}
}
}
//method to find value at particular index in BST
public int findValueAtIndex(Node root,int indexT)
{
index = 0;
return findValueForIndex(root,indexT);
}
//helper method
private int findValueForIndex(Node root,int indexT)
{
if(root == null)
return -1;
int left = findValueForIndex(root.left,indexT);
if(left != -1)
return left;
if(index == indexT)
return root.n;
else
index++;
int right = findValueForIndex(root.right, indexT);
if(right != -1)
return right;
return -1;
}
//method to find total number of nodes
public int numberOfNodes(Node root)
{
if(root == null)
return 0;
if(root.left == null && root.right == null)
return 1;
return 1 + numberOfNodes(root.left) + numberOfNodes(root.right);
}
public static void main(String[] args)
{
Node root = new Node(15);
BinarySearchTree bst = new BinarySearchTree(root);
bst.insert(7);
bst.insert(20);
bst.insert(2);
bst.insert(12);
bst.insert(17);
bst.insert(22);
BSTAndValueXTwoNode value = new BSTAndValueXTwoNode();
value.printTwoNodeValueEqualToX(root,37);
}
/*
Complexity O(nlogn) time.
O(log n) space.
Logic --
If(root < sum)
find in tree sum - root.
if( no answer found in previous step)
repeat this algorithm for left subtree of root.
move to the right subtree of root.
if (root > sum)
move to left subtree.. since all of the values in right subtree and root are useless
*/
Code
void searchSum(bst *head, int sum) {
bst *cand = NULL;
bst *treeHead=head;
while (head) {
if (head->val < sum) {
cand = search(treeHead, sum - head->val);
if (cand && cand!=head) {
cout << "\n"<<head->val << " " << cand->val;
return;
}
}
if (head->val > sum)
head = head->l;
else{
searchSum(head->l,sum);
head = head->r;
}
}
}
Find the least element in BST. Let it be x. Let y = k-x. Find the element that is equal to y or less than y. Traverse in inorder manner from x and in reverse inorder manner from y till either x+y = k or x==y. Use iterative inorder traversal method.
And the iterative (or rather, lazy) traversal can be implemented using yield. (Generator/Coroutines, as some other answer put it).
For all nodes N in BST where N <= x/2
Check if (x-N) exists in the tree
25
16 30
8 20 35
1 10 18 22
24
x=40
All nodes <= 20 are 1, 8, 10, 16, 18, 20
Search for these pairs (1,39), (8,32), (10,30), (16, 24), (18, 22), (20, 20)
Valid if they exist and are distinct node
(10, 30), (16, 24), (18, 22),
(20, 20) points to the same node - hence invalid
//simple code for comparing using left and right stack
//which is basically in order traversing using stack,
//when you are traversing in left subtree using left stack, every
//time pops, push the right child of the current node and all the
//left child of the right child.
Stack left;
while(root!=null){//initialize
left.push(root.l);
root=root.l;}
node root=left.pop();//when comparing using left stack
if(root.right!=null){
left.push(root.r);
root=root.r}
while(root!=null){
left.push(root.l);
root=root.l;}
Test1:
/----9266
/----9223
/----8811
| | /----8731
| | /----8697
| \____8276
/----7853
| | /----7402
| | /----7261
| | /----7190
| | | \____6571
| | /----6232
| | | \____5657
| | /----3826
| | | \____3182
| | | | /----2776
| | | | | \____2549
| | | \____1767
| \____1032
55
Test2:
/----7993
/----7700
| \____7574
| \____7524
7314
| /----5142
| /----4634
| | | /----4225
| | | | \____3711
| | | /----3068
| | | /----2825
| | | | \____2672
| | | /----2514
| | | | \____2117
| | | | \____2009
| | | | | /----1608
| | | | \____1298
| | \____1250
| | \____359
\____22
BOOL TwoNodeSum(NODE *Root, int x, NODE **N1, NODE **N2)
{
NODE *Mn = NULL, *Mx = NULL, *List[HIGHT], *TN = NULl, *TN2 = NULl;
int sum = 0, i = 0;
Mn = min(Root);
Mx = max(Root);
while(Mn->info < Mx->info){
sum = Mn->info + Mx->info;
if(sum == x){
*N1 = Mn;
*N2 = Mx;
return TRUE;
}else if(sum > x){//Get Predecessor of Max Node i.e. of Mx
TN = Root;
i = 0;
while(Mx->info != TN->info){
List[i++] = TN;
if(Mx->info < TN->info) TN = TN->Left;
else TN = TN->Right;
}
PN = List[--i];
if(Mx->Left != NULL){
Mx = max(Mx->Left);
}else if(PN != NULL){
if(PN->Right == Mx) Mx = PN;
else{
TN2 = List[--i];
SWAP(TN2, PN);
while(PN->Left == TN2){
TN2 = List[--i];
SWAP(TN2, PN);
}
Mx = PN;
}
}else{//Get Sucessor of Min Node i.e. of Mn
TN = Root;
i = 0;
while(Mn->info != TN->info){
List[i++] = TN;
if(Mx->info < TN->info) TN = TN->Left;
else TN = TN->Right;
}
PN = List[--i];
if(Mn->Right != NULL){
Mn = min(Mn->Right);
}else if(PN != NULL){
if(PN->Left == Mn) Mn = PN;
else{
TN2 = List[--i];
SWAP(TN2, PN);
while(PN->Right == TN2){
TN2 = List[--i];
SWAP(TN2, PN);
}
Mn = PN;
}
}
}//while
}
bool find2Node(Node* root,double targetV,Node*& n1,Node*& n2){
if(root==NULL)return false;
n1=root,n2=root;
stack<Node*> st1,st2;
bool hasFound=false;
while(true){
while(n1!=NULL){
st1.push(n1);
n1=n1->left;
}
while(n2!=NULL){
st2.push(n2);
n2=n2->right;
}
if(st1.top()==st2.top())break;
double nowV=st1.top()->v+st2.top()->v;
if(nowV<targetV){
n1=st1.top()->right;
st1.pop();
}else if(nowV>targetV){
n2=st2.top()->left;
st2.pop();
}else{hasFound=true;n1=st1.top();n2=st2.top();break;}
}
return hasFound;
}
#include <stack>
using namespace std;
struct tree_node
{
struct tree_node *left;
struct tree_node *right;
int data;
};
void find_tree_sum(struct tree_node *root, int sum, struct tree_node **first, struct tree_node **second)
{
stack<struct tree_node *> small;
stack<struct tree_node *> large;
struct tree_node *temp = root;
while (temp != NULL) {
small.push(temp);
temp = temp->left;
}
temp = root;
while (temp != NULL) {
large.push(temp);
temp = temp->right;
}
*first = *second = NULL;
while (!small.empty() && !large.empty()) {
if (small.top()->data > large.top()->data) {
return;
}
int s = small.top()->data + large.top()->data;
if (s == sum) {
*first = small.top();
*second = large.top();
return;
}
if (s > sum) {
temp = small.top();
if (temp->right != NULL) {
temp = temp->right;
while (temp != NULL) {
small.push(temp);
temp = temp->left;
}
} else {
do {
temp = small.top();
small.pop();
}while (!small.empty() && small.top()->right == temp);
}
} else {
temp = large.top();
if (temp->left != NULL) {
temp = temp->left;
while (temp != NULL) {
large.push(temp);
temp = temp->right;
}
} else {
do {
temp = small.top();
small.pop();
}while (!small.empty() && small.top()->left == temp);
}
}
}
}
Brillant idea of sonesh, and here is my implementation code in C++:
#include <iostream>
#include <stack>
#include <random>
#include <vector>
struct node
{
int data;
node *left, *right;
node( int data, node* left = nullptr, node* right = nullptr ) : data(data), left(left), right(right){}
};
typedef node* BST_Iter;
struct BST
{
private:
void delete_subtree( BST_Iter it )
{
if( it != nullptr )
{
delete_subtree(it->left);
delete_subtree(it->right);
delete it;
}
}
public:
BST_Iter root;
BST() : root(nullptr) {}
~BST(){ delete_subtree(root); }
void push( int v )
{
if( root == nullptr )
{
root = new node(v);
return;
}
BST_Iter prev_it, it = root;
while( it != nullptr )
{
prev_it = it;
if( v <= it->data ) it = it->left;
else it = it->right;
}
if( v < prev_it->data ) prev_it->left = new node(v);
else prev_it->right = new node(v);
}
};
void sum_of_two( const BST& tr, int x ) // time complexity is O(n), because each node at most is push and pop from the stack by once
{
if( tr.root == nullptr ) return;
std::stack<BST_Iter> min_stack, max_stack;
BST_Iter it = tr.root;
while( it != nullptr )
{
min_stack.push(it);
it = it->left;
}
BST_Iter jt = tr.root;
while( jt != nullptr )
{
max_stack.push(jt);
jt = jt->right;
}
it = min_stack.top(), jt = max_stack.top();
min_stack.pop(), max_stack.pop();
BST_Iter kt;
while( it != jt && it->data <= jt->data )
{
if( it->data + jt->data == x ) break;
if( it->data + jt->data < x )
{
kt = it->right;
while( kt != nullptr )
{
min_stack.push(kt);
kt = kt->left;
}
if( min_stack.empty() ) break;
it = min_stack.top();
min_stack.pop();
}
else
{
kt = jt->left;
while( kt != nullptr )
{
max_stack.push(kt);
kt = kt->right;
}
if( max_stack.empty() ) break;
jt = max_stack.top();
max_stack.pop();
}
}
if( it->data + jt->data == x )
std::cout << "Elements : " << it->data << "+" << jt->data << "=" << x << std::endl;
else
std::cout << "No Elements makes the sum : " << x << std::endl;
}
int main( int argc, char* argv[] )
{
int n = 10;
int x;
std::vector<int> vec;
vec.reserve(n);
std::default_random_engine gen;
std::uniform_int_distribution<int> dist( 0, 100 );
std::cout << "Elements : ";
for( int i = 0; i < n; ++i )
{
vec.push_back( dist(gen) );
std::cout << vec.back() << " ";
}
std::cout << std::endl;
while(true)
{
std::cout << "------------------------" << std::endl;
std::cout << "Target : ";
std::cin >> x;
std::cout << std::endl;
BST tr;
for( std::vector<int>::iterator it = vec.begin(); it != vec.end(); ++it ) tr.push(*it);
sum_of_two( tr, x );
std::cout << "------------------------" << std::endl;
}
return 0;
}
import java.util.*;
public class CareerCup_15320677{
public static void main(String[]args){
int[] arr = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
System.out.println(findMatchingPairWithBst(arr, 3));
}
private static Pair findMatchingPairWithBst(int[] arr, int target){
if (arr == null || arr.length == 0) {
return null;
}
Node root = Node.parse(arr);
Deque<Node> leftStack = new LinkedList<Node>();
Deque<Node> rightStack = new LinkedList<Node>();
fillLeft(root, leftStack);
fillRight(root, rightStack);
Node left = nextIncreasing(leftStack);
Node right = nextDecreasing(rightStack);
while(left != right){
int sum = left.val + right.val;
if (sum < target){
left = nextIncreasing(leftStack);
} else if (sum > target){
right = nextDecreasing(rightStack);
} else {
return new Pair(left.val, right.val);
}
}
return null;
}
private static void fillLeft(Node node, Deque<Node> stack){
if (node == null) {
return;
}
while(node != null){
stack.push(node);
node = node.left;
}
}
private static void fillRight(Node node, Deque<Node> stack){
if (node == null){
return;
}
while(node != null){
stack.push(node);
node = node.right;
}
}
private static Node nextIncreasing(Deque<Node> stack){
Node next = stack.pop();
fillLeft(next.right, stack);
return next;
}
private static Node nextDecreasing(Deque<Node> stack){
Node next = stack.pop();
fillRight(next.left, stack);
return next;
}
}
class Pair{
int x, y;
Pair(int x, int y){
this.x = x;
this.y = y;
}
public String toString(){
return String.format("(%d,%d)", x, y);
}
}
class Node{
int val;
Node left;
Node right;
static Node parse(int[] arr){
return parse(arr, 0, arr.length-1);
}
static Node parse(int[] arr, int lo, int hi){
if (lo > hi) {
return null;
}
int mid = lo + (hi-lo)/2;
Node node = new Node();
node.val = arr[mid];
node.left = parse(arr, lo, mid-1);
node.right = parse(arr, mid+1, hi);
return node;
}
}
Working python solution:
class Node:
def __init__(self,val):
self.l_child = None
self.r_child = None
self.val = val
def binary_insert(root,node):
if root is None:
root = node
elif(root.val > node.val):
if(root.l_child == None):
root.l_child = node
else:
binary_insert(root.l_child,node)
else:
if(root.r_child == None):
root.r_child = node
else:
binary_insert(root.r_child,node)
r = Node(8)
binary_insert(r,Node(3))
binary_insert(r,Node(1))
binary_insert(r,Node(6))
binary_insert(r,Node(4))
binary_insert(r,Node(7))
binary_insert(r,Node(10))
binary_insert(r,Node(14))
binary_insert(r,Node(13))
arr1 = []
arr2 = []
def add_to_arr1(node):
if node is None:
return
else:
arr1.append(node)
add_to_arr1(node.l_child)
def add_to_arr2(node):
if node is None:
return
else:
arr2.append(node)
add_to_arr2(node.r_child)
def find_sum(r,x):
if r is None:
return
add_to_arr1(r.l_child)
add_to_arr2(r)
while(arr1 and arr2):
if(arr1[-1].val + arr2[-1].val > x):
if(arr2[-1].l_child is None):
arr2.pop()
else:
a=arr2.pop()
arr2.append(a.l_child)
elif(arr1[-1].val + arr2[-1].val < x):
if(arr1[-1].r_child is None):
arr1.pop()
else:
a=arr1.pop()
arr1.append(a.r_child)
else:
print("result found. {} and {} sum up to {}".format(arr1[-1].val,arr2[-1].val,x))
return [arr1[-1],arr2[-1]]
break
result = find_sum(r,11)
if result is None:
print("Search not successful")
Same solution as most guys but Python's iterator using the yield makes it particularity simpler to write out:
class Node:
def __init__(self, value):
self.left_child = None
self.right_child = None
self.value = value
def insert(self, value):
if value < self.value:
if self.left_child is None:
self.left_child = Node(value)
else:
self.left_child.insert(value)
else:
if self.right_child is None:
self.right_child = Node(value)
else:
self.right_child.insert(value)
def __repr__(self):
return "<" + str(hex(id(self))) + ">(" + str(self.value) + ")"
def min_iterator(self):
if self.left_child:
for node in self.left_child.min_iterator():
yield node
yield self
if self.right_child:
for node in self.right_child.min_iterator():
yield node
def max_iterator(self):
if self.right_child:
for node in self.right_child.max_iterator():
yield node
yield self
if self.left_child:
for node in self.left_child.max_iterator():
yield node
def tree_from_list(lst):
root = Node(lst[0])
for item in lst[1:]:
root.insert(item)
return root
def find_pair(root, sum_value):
min_iter, max_iter = root.min_iterator(), root.max_iterator()
min_node = next(min_iter)
max_node = next(max_iter)
while True:
if min_node is max_node:
return None, None
cur_sum = min_node.value + max_node.value
if cur_sum == sum_value:
return min_node, max_node
elif cur_sum > sum_value:
max_node = next(max_iter)
elif cur_sum < sum_value:
min_node = next(min_iter)
tree = tree_from_list([60, 41, 74, 16, 53, 65, 25, 46, 55, 63, 70, 42, 62, 64])
print find_pair(tree, 41 + 74)
Here is the logic for the case where all node values are positive.
Starting from root node,
IF (x <= root node value), then required two nodes with sum of values equals to x, if exists, will definitely be in left sub-tree of root
ELSE required two nodes can be in either of left or right sub-tree, in which case, find node with value (x - root.value) in tree rooted at root.
People who don't understand should not downvote. This is an excellent (though cryptic) answer.
struct node *temp = head;
void find_node(struct node *head,int sum)
{
if(head == NULL)
{
return;
}
find_node(head->left,sum);
if(Nested_find_node(temp,(sum-(head->data))) == SUCCESS)
{
Printf("The Second Node of Pair%d",head->data);
return;
}
find_node(head->left,sum);
}
int Nested_find_node(struct node *head,int X)
{
if(head == NULL)
{
return;
}
Nested_find_node(head->left,X);
if(head->data == X)
{
Printf("The First Node of Pair%d",head->data);
return SUCCESS;
}
Nested_find_node(head->left,X);
}
its like doing Nested Inorder inside Inorder and searching the element sum-X. (X= every node of the element)Complexity((logn)(log(n)) without extra apace ...
Your code have many bugs. Also I think your code will loop infinitely. As both functions are calling each other.
@nitin : it is just a kind of an algo..not proper code..so all boundary value cases not handled....Please let me know if any issue with Logic of an Algo..
@ravisingh: for every node you are checking the left and right subtree to see if it is equal to sum - current_node.
I think it will fit the bill.
@raviSingh - In method Nested_find_node(), you need to add check to ensure that (temp != head).
This brute force logic is coded well by
- annn on February 18, 2013
after your post.
but the size of you hash is O(n) while there is a space restriction O(height of the tree)
You don't need a hash, use two iterators one inorder (starts at min) and one reverse inorder (starts at max). Here is the C++ code, the operators ++ just return the successor in the given order. You can change the code to output one pair, unique pairs, all pair
// output unique pairs that sum to sum
void FindNodesWithSum(BinarySearchTree *tree, int sum)
{
InorderTraversal pre(tree);
OutoforderTraversal post(tree);
TreeNode *p, *q;
p=++pre;q=++post;
while(p && q &&p->Value()<=q->Value())
{
int sum0 = p->Value() + q->Value();
if (sum0>sum) {q=++post; }
else if (sum0<sum) { p=++pre; }
else
{
std::cout<<p->Value()<<","<<q->Value()<<"\n";
TreeNode *p0 = ++pre;
while (p0 && p->Value()==p0->Value())
{
p0=++pre;
}
TreeNode* q0 = ++post;
while (q0 && q->Value()==q0->Value())
{
q0=++post;
}
p=p0;
q=q0;
}
};
}
solution : having complexity O(n)(time)+O(height of BST)(space)
observation : if we are given a sorted array instead of a BST and the same question was asked then so solve this problem in O(n)+O(1) complexity, we keep two indexes one at start and 2nd one at end, and apply following algo.
if(A[1st_index] + A[2nd_index] < x) 2nd_index--; else if (A[1st_index] + A[2nd_index] > x) 1st_index++; else print 1st_index,2nd_index; do this until 2nd_index > 1st_indexso we apply the same concept here, because we don't have data stored in an array faction, so we need some space, now one way is tot store the data into an array and apply the same, but this require O(n) space, but if you think carefully, then we only require at max 2*height_of_BST, in first array of size height_of_BST, we store all elements which comes from
and in 2nd array we store
and we start with the last element of these two array, these array's are actually stack. now we get two element do we do the same comparison here also
- sonesh January 26, 2013if(first_stack_element + 2nd_stack_element < x) check for it's left tree, and store all right going element into stack(2nd stack) and start again example : \ 6 / 3 / \ 1 4 so we store [.......3,4] after popging 6. because now 4 is the biggest element in the tree. actually we search for last biggest element here. else if (first_stack_element + 2nd_stack_element > x) Here we search for next smallest element, using our 1st stack. example / 2 \ 6 / \ 3 7 now here we go with 3 for next comparison.and the stack contain [.....,6,3] after popping 2 else print first_stack_element, 2nd_stack_element; do this until first_stack_element < 2nd_stack_element