JIYIK CN >

The in-order descendant of a binary tree is the next node in the in-order traversal of the binary tree. So, for the last node in the tree, it is NULL. Since the in-order traversal of a binary search tree is a sorted array. The node with the smallest key greater than a given node is defined as its in-order descendant. In a BST, there are two possibilities for an in-order descendant, namely, the node with the smallest value in the right subtree or ancestor of the node. Otherwise, the in-order descendant of the node does not exist.

In-order descendant algorithm in BST algorithm

• If root= NULL, then succset to NULLand return .
• If root->data< current->data, then succis current, currentand is current->left.
• If root->data> current->data, then currentis current->right.
• If root->data== current->dataand root->right!= NULL, succ= minimum(current->right).
• return succ.

Diagram of in-order descendants in a BST

3The in-order descendants of are 4, because 3has a right node that is the smallest node 4in the right subtree that is larger than .3

4The sequential descendants of are 5, since 4has no right node, we need to look at its ancestors, where 5is 4the smallest node larger than .

Implementation of BST in-order descendants

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node *left, *right;
    Node(int x) {
        this->data = x;
        this->left = this->right = NULL;
    }
};

Node* insert(Node* root, int key)
{
    if (root == NULL) {
        return new Node(key);
    }
    if (key < root->data) {
        root->left = insert(root->left, key);
    }
    else {
        root->right = insert(root->right, key);
    }
    return root;
}

Node* getNextleft(Node* root)
{
    while (root->left) {
        root = root->left;
    }

    return root;
}

void inorderSuccessor(Node* root, Node*& succ, int key)
{

    if (root == NULL) {
        succ = NULL;
        return;
    }

    if (root->data == key)
    {
        if (root->right) {
            succ = getNextleft(root->right);
        }
    }

    else if (key < root->data)
    {
        succ = root;
        inorderSuccessor(root->left, succ, key);
    }
    else {
        inorderSuccessor(root->right, succ, key);
    }
}

int main()
{
    int keys[] = { 1, 5, 8, 2, 6, 3, 7, 4 };
    Node* root = NULL;
    for (int key : keys) {
        root = insert(root, key);
    }
    for (int key : keys)
    {
        Node* prec = NULL;
        inorderSuccessor(root, prec, key);
        if (prec) {
            cout << "Inorder successor of node " << key << " is " << prec->data;
        }
        else {
            cout << "No inorder Successor of node " << key;
        }

        cout << '\n';
    }

    return 0;
}

Algorithmic complexity of finding in-order descendants in BST

Time Complexity

• Average situation

On average, the time complexity of finding an in-order descendant in a BST is comparable to the height of the binary search tree. On average, the height of a BST is O(logn). This occurs when the resulting BST is a balanced BST. Therefore, the time complexity is [Big Theta]: O(logn).

• Best Case

The best case is when the tree is a balanced BST. In the best case, the time complexity of deletion is O(logn). It is the same as the time complexity of the average case.

• Worst case scenario

In the worst case, we may need to go from the root node to the deepest leaf node, which is the entire height of the tree h. If the tree is unbalanced, i.e. it is skewed, the height of the tree may become n, so the worst case time complexity of insertion and search operations is O(n).

Space complexity

Due to the additional space required for the recursive calls, the space complexity of this algorithm is O(h).