Inorder successor of a node

In Binary Search Tree, Inorder Successor of
an input node can also be defined as the node with the smallest key greater than the key of input node. So, it is sometimes important to find next node in sorted order.

In the above diagram, inorder successor of 8 is 10, inorder successor of 10 is 12 and inorder successor of 14 is 20.Write a code for this.

Comments

  1. Traverse nodes in reverse inorder manner, and populate the successor field for each node.

    void Reverse_Inorder(struct Node* pRoot, Node*& Succ)
    {
    if (!pRoot)
    return;
    Reverse_Inorder(pRoot->right, Succ);
    pRoot->next = Succ;
    Succ = pRoot;
    Reverse_Inorder(pRoot->left, Succ);
    }

    Initially
    Reverse_Inorder(root, NULL);

    ReplyDelete

Post a Comment

Popular posts from this blog

Circular game survival