iTribe Interview Question Solution

solution.cpp

#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;
}

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