# Find the preorder successor of all the nodes in a BST

**Introduction**

Before beginning with this question, let’s recap what a BST is and what we mean by a pre-order successor of a node.

**BST** is a unique binary tree where each node contains a value greater than all the values present in the left subtree and smaller than or equal to the values present in the right subtree.

Example -

**The pre-Order successor of a node in a Binary Tree** is the node next to the current node in the pre-order traversal of a binary tree.

For example :

**Preorder traversal of the above tree is: 30 20 10 15 25 23 39 35 42**

Therefore preorder successor for 20 will be 10, 23 will be 39, etc.

**Problem Statement**

You are given a Binary Search Tree (BST) where you have to find the pre-order successor of all the nodes.

Example:

**Input** - above Tree

**Output** -

```
Pre-order successors of all the nodes are :
Pre-order successor of 30 is 20
Pre-order successor of 20 is 10
Pre-order successor of 10 is 15
Pre-order successor of 15 is 25
Pre-order successor of 25 is 23
Pre-order successor of 23 is 39
Pre-order successor of 39 is 35
Pre-order successor of 35 is 42
Pre-order successor of 42 doesn't exist
```

**Approach**

The question is straightforward as we just need to store the pre-order traversal of the BST in an array. Next, we can easily find the pre-order 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<<"Pre-order successor of all the nodes are : "<<endl;
for(int i=0;i<preOrder.size()-1;i++){
cout<<"Pre-order successor of "<<preOrder[i]<<" is "<<preOrder[i+1]<<endl;
}
// Since there won't be any pre-order successor for the last element in the pre-order traversal
cout<<"Pre-order successor of "<<preOrder[preOrder.size()-1]<<" doesn't exist"<<endl;
}
```

**Time Complexity **

Since we traverse the whole tree only once to find its pre-order, T(n) = O(n), where n = the total number of nodes in a tree.

**Space Complexity **

We store the pre-order traversal of an array. Therefore space complexity is O(n), where n = Total number of nodes in a tree.

**Frequently Asked Question**

**1. 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.

**2. 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.

**Key Takeaways**

This article taught us how to to do a pre-order traversal of a Binary Search Tree with all the essential concepts. We also learned how do we pass arguments in a function by reference.

Since Binary Search Tree is frequently asked in interviews, we recommend you practice more problems based on __Binary Search Trees__ on CodeStudio.

Comments

## No comments yet

## Be the first to share what you think