Approach
The question is straightforward as we just need to store the preorder traversal of the BST in an array. Next, we can easily find the preorder successor of a node:
The preorder successor of a node(at the ith index ) will be present at the (i+1)th index in the array.
Note: The array passed to the arguments to store the preorder traversal should always be passed as a reference.
Code in C++
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
class TreeNode{
public:
int value;
TreeNode *left , *right;
TreeNode(int value){
this>value = value;
left = NULL;
right = NULL;
}
};
void findPreOrder(TreeNode* root,vector<int>& preOrder){
if(root==NULL){
return;
}
preOrder.push_back(root>value);
findPreOrder(root>left,preOrder);
findPreOrder(root>right,preOrder);
}
int main(){
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
// INPUT TREE
// 30
// / \
// 20 39
// / \ / \
// 10 25 35 42
// \ /
// 15 23
TreeNode* root = new TreeNode(30);
root>left = new TreeNode(20);
root>right = new TreeNode(39);
root>left>left = new TreeNode(10);
root>left>right = new TreeNode(25);
root>right>left = new TreeNode(35);
root>right>right = new TreeNode(42);
root>left>left>right = new TreeNode(15);
root>left>right>left = new TreeNode(23);
// finding the preorder traversal of the tree
vector<int> preOrder;
findPreOrder(root,preOrder);
cout<<"Preorder successor of all the nodes are : "<<endl;
for(int i=0;i<preOrder.size()1;i++){
cout<<"Preorder successor of "<<preOrder[i]<<" is "<<preOrder[i+1]<<endl;
}
// Since there won't be any preorder successor for the last element in the preorder traversal
cout<<"Preorder successor of "<<preOrder[preOrder.size()1]<<" doesn't exist"<<endl;
}
Time Complexity
Since we traverse the whole tree only once to find its preorder, T(n) = O(n), where n = the total number of nodes in a tree.
Space Complexity
We store the preorder traversal of an array. Therefore space complexity is O(n), where n = Total number of nodes in a tree.
Also check out  Inorder Predecessor
Frequently Asked Questions
What is a BST (Binary Search Tree)?
BST is a binary tree in which every node of the tree should satisfy these two properties:
 All the nodes in the left subtree should have lesser values than the value at the current node.

All the nodes in the right subtree should have values that are either equal to or more than the value at the current node.
What does pass by reference mean in C++?
Pass by reference means passing the reference of an argument to the function. Since its reference is passed, the calling function can directly change the value at that reference.
Conclusion
This article taught us how to to do a preorder traversal of a Binary Search Tree with all the essential concepts. We also learned how do we pass arguments in a function by reference.
Recommended Reading:
Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.
Since Binary Search Tree is frequently asked in interviews, we recommend you practice more problems based on Binary Search Trees on Coding Ninjas Studio.