1. Problem Description
This is
a Facebook interview question for software engineer from careercup. Here is the original thread,
"
Find the in-order successor of a node in BST
- Kiara 2 months ago in United States | Report Duplicate | Flag "
2. Analysis
The following picture shows the cases of the in-order successor of node "X".
 |
| Node X's in-order success in BST |
3. C++ Implementation
// ********************************************************************************
// Implementation
// ********************************************************************************
#include <cassert>
#include <memory>
#include <queue>
#include <stack>
#include <vector>
template<typename T>
struct TreeNode
{
TreeNode(const T& d)
: data(new T(d)), left(nullptr), right(nullptr)
{}
~TreeNode()
{
std::shared_ptr<T>().swap(data);
}
std::shared_ptr<T> data;
TreeNode* left;
TreeNode* right;
};
template<typename T>
struct TreeConstructionBFS
{
TreeConstructionBFS()
{}
TreeConstructionBFS(TreeNode<T>* p, bool left, int s, int e)
: parent(p), isLeftChild(left), start(s), end(e)
{}
TreeNode<T>* parent = nullptr;
bool isLeftChild = false;
int start = 0;
int end = -1;
};
template<typename T>
struct TreeConstructionDFS
{
TreeConstructionDFS()
{}
TreeConstructionDFS(TreeNode<T>** n, int s, int e)
: node(n), start(s), end(e)
{}
TreeNode<T>** node = nullptr;
int start = 0;
int end = -1;
};
// Create BST based on sorted input via BFS
template<typename T>
TreeNode<T>* ConstructTreeOnSortedValueBFS(const std::vector<T>& input)
{
if (input.empty()) {
return nullptr;
}
const int len = input.size();
int index = len >> 1;
TreeNode<T>* root = new TreeNode<T>(input[index]);
std::queue<TreeConstructionBFS<T>> nodesToBuild;
nodesToBuild.push(TreeConstructionBFS<T>(root, true, 0, index - 1));
nodesToBuild.push(TreeConstructionBFS<T>(root, false, index + 1, len - 1));
while (!nodesToBuild.empty()) {
const TreeConstructionBFS<T>& curCon = nodesToBuild.front();
if (curCon.start > curCon.end) {
if (curCon.isLeftChild) {
curCon.parent->left = nullptr;
}
else {
curCon.parent->right = nullptr;
}
}
else {
index = (curCon.start + curCon.end) >> 1;
TreeNode<T>* tempNode = new TreeNode<T>(input[index]);
if (curCon.isLeftChild) {
curCon.parent->left = tempNode;
}
else {
curCon.parent->right = tempNode;
}
nodesToBuild.push(TreeConstructionBFS<T>(tempNode,
true,
curCon.start,
index - 1));
nodesToBuild.push(TreeConstructionBFS<T>(tempNode,
false,
index + 1,
curCon.end));
}
nodesToBuild.pop();
}
return root;
}
// Create BST based on sorted input via DFS
template<typename T>
TreeNode<T>* ConstructTreeOnSortedValueDFS(const std::vector<T>& input)
{
if (input.empty()) {
return nullptr;
}
const int len = input.size();
int index = len >> 1;
TreeNode<T>* root = new TreeNode<T>(input[index]);
std::stack<TreeConstructionDFS<T>> nodesToBuild;
nodesToBuild.push(TreeConstructionDFS<T>(&root->left, 0, index - 1));
nodesToBuild.push(TreeConstructionDFS<T>(&root->right, index + 1, len - 1));
while (!nodesToBuild.empty()) {
const TreeConstructionDFS<T>& curCon = nodesToBuild.top();
if (curCon.start > curCon.end) {
*(curCon.node) = nullptr;
nodesToBuild.pop();
}
else {
index = (curCon.start + curCon.end) >> 1;
TreeNode<T>* tempNode = new TreeNode<T>(input[index]);
*(curCon.node) = tempNode;
TreeConstructionDFS<T> left(&tempNode->left,
curCon.start,
index - 1);
TreeConstructionDFS<T> right(&tempNode->right,
index + 1,
curCon.end);
nodesToBuild.pop();
nodesToBuild.push(left);
nodesToBuild.push(right);
}
}
return root;
}
// Free the resource
template<typename T>
void DeleteTree(TreeNode<T>** root)
{
TreeNode<T>* curNode = *root;
if (curNode != nullptr) {
TreeNode<T>* left = curNode->left;
TreeNode<T>* right = curNode->right;
delete curNode;
curNode = nullptr;
DeleteTree(&left);
DeleteTree(&right);
}
}
// Find "X" in BST
template<typename T>
bool FindPath(TreeNode<T>* root, const T& val, std::stack<TreeNode<T>*>& path)
{
TreeNode<T>* curNode = root;
std::stack<TreeNode<T>*> result;
bool found = false;
while (curNode != nullptr) {
result.push(curNode);
const T& curVal = *curNode->data.get();
if (curVal == val) {
found = true;
break;
}
if (curVal > val) {
if (curNode->left == nullptr) {
break;
}
curNode = curNode->left;
}
else {
if (curNode->right == nullptr) {
break;
}
curNode = curNode->right;
}
}
if (found) {
path.swap(result);
}
return found;
}
// Find the leftest node given a root
template<typename T>
std::shared_ptr<T> FindLeftestNode(TreeNode<T>* root)
{
TreeNode<T>* curNode = root;
while (curNode->left != nullptr) {
curNode = curNode->left;
}
return curNode->data;
}
template<typename T>
std::shared_ptr<T> NextInOrder(TreeNode<T>* root, const T& val)
{
std::stack<TreeNode<T>*> path;
if (!FindPath(root, val, path)) {
return std::shared_ptr<T>();
}
TreeNode<T>* curNode = path.top();
assert(*curNode->data.get() == val);
if (curNode->right != nullptr) {
// Case 1
return FindLeftestNode(curNode->right);
}
path.pop();
// Case 2
TreeNode<T>* parentNode;
while (!path.empty())
{
parentNode = path.top();
if (parentNode->left == curNode) {
return parentNode->data;
}
curNode = parentNode;
path.pop();
}
// Case 2: can't find Pn
return std::shared_ptr<T>();
}
// ********************************************************************************
// Test
// ********************************************************************************
void TestCasesOfNextInOrder()
{
const std::vector<int> testInput{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
TreeNode<int>* rootBFS = ConstructTreeOnSortedValueBFS(testInput);
assert(rootBFS != nullptr);
auto nextInOrder = NextInOrder(rootBFS, 0);
assert(nextInOrder.get() == nullptr);
nextInOrder = NextInOrder(rootBFS, 1);
assert(*nextInOrder == 2);
nextInOrder = NextInOrder(rootBFS, 2);
assert(*nextInOrder == 3);
nextInOrder = NextInOrder(rootBFS, 3);
assert(*nextInOrder == 4);
nextInOrder = NextInOrder(rootBFS, 4);
assert(*nextInOrder == 5);
nextInOrder = NextInOrder(rootBFS, 5);
assert(*nextInOrder == 6);
nextInOrder = NextInOrder(rootBFS, 6);
assert(*nextInOrder == 7);
nextInOrder = NextInOrder(rootBFS, 7);
assert(*nextInOrder == 8);
nextInOrder = NextInOrder(rootBFS, 8);
assert(*nextInOrder == 9);
nextInOrder = NextInOrder(rootBFS, 9);
assert(*nextInOrder == 10);
nextInOrder = NextInOrder(rootBFS, 10);
assert(nextInOrder.get() == nullptr);
nextInOrder = NextInOrder(rootBFS, 11);
assert(nextInOrder == nullptr);
TreeNode<int>* rootDFS = ConstructTreeOnSortedValueDFS(testInput);
assert(rootDFS != nullptr);
nextInOrder = NextInOrder(rootDFS, 0);
assert(nextInOrder.get() == nullptr);
nextInOrder = NextInOrder(rootDFS, 1);
assert(*nextInOrder == 2);
nextInOrder = NextInOrder(rootDFS, 2);
assert(*nextInOrder == 3);
nextInOrder = NextInOrder(rootDFS, 3);
assert(*nextInOrder == 4);
nextInOrder = NextInOrder(rootDFS, 4);
assert(*nextInOrder == 5);
nextInOrder = NextInOrder(rootDFS, 5);
assert(*nextInOrder == 6);
nextInOrder = NextInOrder(rootDFS, 6);
assert(*nextInOrder == 7);
nextInOrder = NextInOrder(rootDFS, 7);
assert(*nextInOrder == 8);
nextInOrder = NextInOrder(rootDFS, 8);
assert(*nextInOrder == 9);
nextInOrder = NextInOrder(rootDFS, 9);
assert(*nextInOrder == 10);
nextInOrder = NextInOrder(rootDFS, 10);
assert(nextInOrder.get() == nullptr);
nextInOrder = NextInOrder(rootDFS, 11);
assert(nextInOrder == nullptr);
DeleteTree(&rootBFS);
DeleteTree(&rootDFS);
}
