## Interview Questions

### Tree successor

Given binary search tree and node in a tree, find next node (successor). Successor of a node is the next node in inorder traversal of the Binary Tree.

View Solution

#### Algorithm concept

In order to design this algorithm it is best to start with very simple tree and check what different combinations we can have.

Once we do this we can find the following possibilities:

- Element does not have children - successor is parent, for whom we are in his left subtree
- Element does have left child only - successor is parent, for whom we are in his left subtree
- Element has right child - successor is left most (smallest) element in the tree of the right child

#### Solution

struct element *min_tree_search(struct element *node)
{
while (node->left == nullptr) return node;
return min_tree_search(node->left);
}
struct element *tree_successor(struct element *node)
{
if (node->right != nullptr)
{
return min_tree_search(node->right);
}
struct element *tmpParent = node->parent;
while (tmpParent != nullptr && node = tmpParent->right)
{
tmpParent = node->parent;
}
return tmpParent;
}