Created
October 5, 2021 07:54
-
-
Save Sirius-Coder/18bcdd73e9bd52927b927b73c3898693 to your computer and use it in GitHub Desktop.
iTribe Interview Question Solution
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <bits/stdc++.h> | |
using namespace std; | |
//The TreeNode Definition | |
struct TreeNode{ | |
int val; | |
TreeNode *left , *right; | |
} | |
//Function to create a new Node | |
TreeNode* createNode(TreeNode *root,int val){ | |
if(root==NULL) | |
{ | |
TreeNode *temp = new TreeNode(); | |
temp->data=val; | |
temp->left=temp->right=NULL; | |
root=temp; | |
} | |
else if (val<=root->data) | |
{ | |
root->left = insertNode(root->left,val); | |
} | |
else | |
root->right=insertNode(root->right,val); | |
return root; | |
} | |
vector<int> findPair (TreeNode *root , int target){ | |
stack<TreeNode*>s1,s2; // where s1 is the inorder traversal for left pointer and s2 is the reverse inorder traversal for right pointer | |
TreeNode *curr1 = root ,*curr2=root; | |
int val1=0 , val2=0; | |
bool finished1=false , finished2=false; | |
//Infinite loop that will only break when we find a pair of either one of the inorder traversal finishes | |
while(1){ | |
//normal inorder to set the left boundary | |
while(finished1==false){ | |
if(curr1!=NULL) | |
{ | |
s1.push(curr1); | |
curr1=curr1->left; | |
} | |
else{ | |
if(!s1.empty()){ | |
curr1=s1.top(); | |
s1.pop(); | |
val1=curr1->val; | |
curr1=curr1->right; | |
} | |
else | |
finished1=true; | |
} | |
} | |
//reverse inorder to set the right boundary | |
while(finished2==false){ | |
if(curr2!=NULL) | |
{ | |
s2.push(curr1); | |
curr2=curr2->right; | |
} | |
else{ | |
if(!s2.empty()){ | |
curr2=s2.top(); | |
s2.pop(); | |
val2=curr2->val; | |
curr2=curr2->left; | |
} | |
else | |
finished1=true; | |
} | |
} | |
if(val1!=val2 && val1+val2==target){ | |
return {val1,val2}; | |
} | |
else if(val1+val2<target) | |
finished1=false; //if current sum less than target increment the left boundary | |
else if (val1+val2>target) | |
finished2=false; | |
if(finished1==true || finished2==true) | |
return {} ; //If any of the inorder traversal is over return an empty array | |
} | |
} | |
int main(){ | |
TreeNode *root=NULL; | |
//Create as many nodes using this way | |
root = createNode(root,4); //Use any val here instead of 4 | |
vector<int>res; | |
res = findPair(root,18) // The second argument is the target sum; | |
//This will return an array | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
The main thing that I was missing here was to have both the states of the inorder/reverse inorder at the same time , and during interview I was only thinking of the recursive approach but if we implement that iteratively then we can achieve the optimal solution