CODEWITHSUNDEEP
binary-search-treeinorder
mico
mico

Reputation: 19

Inorder successor of a binary tree (NOT BST)

Can someone help me to figure out how to find inorder successor of a binary tree for a given node(not a binary search tree)? I know how to find it in a binary search tree: It will be the left-most leaf of the right subtree. However, I am not sure how it is done if the tree is not a BST.

I don't think I can go to the right child and then to the leftmost leaf node. (OR is there a difference between finding inorder successor in a BST and normal BT)?

Thank you.

Upvotes: 1

Views: 387

Answers (2)

Anshul Sharma
Anshul Sharma

Reputation: 1

We can write a recursive function to find the in-order successor of a binary tree. The time complexity will be O(n), where n -> number of nodes in the binary tree. This is much greater than in the case of BST, where time complexity was O(log(n)) as we can reject either the left or right subtree in each call.

Here's the code, we maintain the next pointer which has the value of the successor of the current node. We first move to the right child, then process, and then to the left child. Note that whenever we find the node whose successor we are searching for, we will return the next and will not process further.

class Solution {
private:
    TreeNode* fun(TreeNode* node, TreeNode* p, TreeNode* &next) {
        if (!node) 
            return NULL;
    
        TreeNode* right = fun(node->right, p, next);
        if (right) return right;
        if (node == p) return next;
        next = node;

        TreeNode* left = fun(node->left, p, next);
        if (left) return left;
        return NULL;
    }
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        if (!root || !p)
            return NULL;
        TreeNode* next = NULL;
        return fun(root, p, next);
    }
};

Upvotes: 0

trincot
trincot

Reputation: 350781

Is there a difference between finding inorder successor in a BST and normal BT?

No, there isn't. An inorder ordering is one that applies to binary trees in general.

The only difference in effect, is that an inorder traversal on a BST will produce a sequence of values that is ordered by value. But that is just a nice property that applies to a BST. It does not affect the meaning of what inorder represents.

Upvotes: 0

Related Questions