int preIndex = 0;

int search(int In[], int startIn,int endIn, int data)    // search for the element in inorder array
{
    int i = 0;
    for (i = startIn; i < endIn; i++)
    {
        if (arr[i] == data)
        {
            return i;
        }
    }
    return i;
}
void printPost(int In[], int pre[],int inStrt, int inEnd)
{
    if (inStrt > inEnd)
    {
        return;
    }
    int inIndex = search(arr, inStrt, inEnd,pre[preIndex++]);   // found A
 
    // traverse left tree
    printPost(arr, pre, inStrt, inIndex — 1);     // doing same thing for DBE
 
    // traverse right tree
    printPost(arr, pre, inIndex + 1, inEnd);      // doing same thing for FC
 
    // print root node at the end of traversal
    cout << arr[inIndex] << " ";                  // priting root at last
}

int preIndex=0; {note: here we were traversing on in-order}
struct Node* buildTree(char in[], char pre[], int inStrt,int inEnd, unordered_map& mp)
{
	if (inStrt > inEnd)
		return NULL;
	char curr = pre[preIndex++];
	struct Node* tNode = newNode(curr);
	if (inStrt == inEnd)     // if the node has no child
		return tNode;
	int inIndex = mp[curr];
	tNode->left = buildTree(in, pre, inStrt, inIndex — 1, mp);
	tNode->right = buildTree(in, pre, inIndex + 1, inEnd, mp);

	return tNode;  // final point we reached
}
struct Node* buldTreeWrap(char in[], char pre[], int len)
{
	unordered_map mp;
	for (int i = 0; i < len; i++)
		mp[in[i]] = i;

	return buildTree(in, pre, 0, len - 1, mp);
}

 int postIndex;
 TreeNode* buildTree(vector&in,vector&pos, int inStrt,int inEnd, unordered_map& mp)
{
    if (inStrt > inEnd)
        return NULL;
    int  curr = pos[postIndex];
    TreeNode* tNode = new TreeNode(curr);
    postIndex--;
    if (inStrt == inEnd)     // if the node has no child
        return tNode;
    int inIndex = mp[curr];
    tNode->right = buildTree(in, pos, inIndex + 1, inEnd, mp);
    tNode->left = buildTree(in, pos, inStrt, inIndex — 1, mp);
    return tNode;  // final point we reached
}

Parent is smaller than it's right child but bigger than it's left child"

Now the 1st smallest element will be the first value of Inorder [lcr(left-center-right)] then 2nd smallest is 1st smallest's parent and 3rd smallest is 2nd second smallest's right child so it is like inorder traversal so just do Left-child-right and find out the kth element from the array of inorder traversal

o(n) time complexity

Pre-order traversal

Now simple do Pre-order traversal(you can do any other traversal also) then use unordered_map to store the values, now if the Now as A+B=K then we can do A=k-B so yes if for B if there is any A present then we are done , if not present then store the B value maybe in future we can find the A

 int ans;unordered_map<int,int>m;
void preorder(TreeNode* &A,int B){
if(A==NULL)return;

 if(m.find((B-(A->val)))!=m.end()){
     ans=1;
     return;
 }
 else m[(A->val)]=1;

 preorder(A->left,B);

 preorder(A->right,B);
} 

 int Solution::t2Sum(TreeNode* A, int B) {
preorder(A,B);

int final_ans=ans;

return final_ans;
} 

1st element is root

Now as we discussed that from i+1 to n for a given i in pre-order there is a point "U' where from i+1 to U-1 , all elements are left subtree of root and from U to n all are right subtree, where 2<=U<=n+1,, n+1 means there is no right element n

now when got the U , for root at a[0] then there will be another U for a[1] as a[1] will be the root of left subtree and a[U] will be the root of right subtree

int find(int i, int j, vector&v){

if(i>=j)  // if intial and final value crossed then return 1 

return 1;

int k;

for( k=i+1;k<=j;k++){ // now finding that U we have discussed in hints which differentiate the left subtree and right subtree

if(v[k]>v[i]){
break;
}   // k is the differentiation point , it is the U
}

for(int l=k;l<=j;l++){

if( v[l] < v[i] ) return 0 ;     //  now all elements should be greater than v[i] here from k(U) ,so if fails then ans is no!

}
return find(i+1,k-1,v) && find(k,j,v);  // again check for it's subtree from i +1 to k-1 and k to j 
}

Now we know height of balanced Tree is o(logn) and array is sorted then yes! we will use binary search for it or you may say divide and conquer , as in binary search we are always at middle element and then divide the array in 2 halfs , left and right that's what we are doing here

Now Generally Inorder Traversal is sorted in BST but here it will not be sorted now , if the misplaced nodes are adjacent then this case will form {1,2,4,3} then we could simple 4 and 3 is answer but if the misplaced nodes are not adjacent then this type of case will be formed {1,2,8,3,4,5,6,7,2} now 8 and 2 are misplaced then we can also find it by doing O(N) time complexity and 0(N) space complexity we can do this o(1) by Morris Algorithm.

Now in this , the parent will be greater than it's children then from 0 to n , max number will be the root of the tree, then it's left side is left subtree and it's right side is right subtree then we would do same with those subtrees by recursion

int large(vector&v,int s,int e) // Function to find the index of the largest element in the vector
{
    int ans=-1,el=INT_MIN;
    for(int i=s;i<=e;i++)
    {
        if(v[i]>el)
        {
            el=v[i];
            ans=i;
        }
    }
    return ans;
}
void helper(TreeNode* &temp,vector&v,int s,int e)
{
    if(s>e)
    {
        return;
    }
    int index=large(v,s,e);
    TreeNode *k=new TreeNode(v[index]);
    temp=k;
    if(s==e)
    {
        
        return;
    }
    else
    {
        helper(temp->left,v,s,index-1);
        helper(temp->right,v,index+1,e);
    }
}
TreeNode* Solution::buildTree(vector &A) 
{ 
    TreeNode* temp=NULL;
    helper(temp,A,0,A.size()-1);
    return temp;
}

void preOrder(struct Node *root)
{
	stack s;
	Node *curr = root;

	while (curr != NULL || s.empty() == false)
	{
		while (curr != NULL)
		{
                        **cout << curr->data << " ";** // this is simple edit done from the INorder one 
			s.push(curr);
			curr = curr->left;
		}
		curr = s.top();
		s.pop();
		curr = curr->right;
}

vector < TreeNode *>v;
    for(int i=0;i< v.size();i++)
    {
        v[i]->left=NULL;
        v[i]->right=(i==v.size()-1?NULL:v[i+1]);
    }

We can also connect trees like this !