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 - 

Source

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:

1. All the nodes in the left subtree should have lesser values than the value at the current node.
2. 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.