Given the root of a binary tree and a node in it, return the in-order successor of that node in the BST. If the given node has no in-order successor in the tree, return null. The successor here means that the node will be traversed next in an inorder manner for the given node value.
The first solution or the simplest solution that comes to mind when solving inorder successor problem is:
According the the example:
inorder traversal is computed as:
inorderArr = [6, 4, 2, 5, 1, 3]
Now, The successor of node
5 will be
1 occurs right next to
O(n)Because we have to inorder traverse the tree and then iterate over the array to find the desired value.
To get the inorder successor of a Binary Tree, we need to take care of 3 steps:
not NULL. If the right child of the node is not NULL then the inorder successor of this node will be the
leftmost nodein it's right subtree.
is NULL. If the right child of node is NULL. Then we keep finding the parent of the given target node, such that
targetNode.left = x. For example in the above given tree, inorder successor of node
1. First parent of 5 is 2 but
2->left != 5. So next parent of 2 is 1, now 1->left = 2. Therefore, inorder successor of 5 is 1.
rightmost node. If the node is the rightmost node in the given tree. For example, in the above tree node
3is the right most node. In this case, there will be no inorder successor of this node. i.e. Inorder Successor of the rightmost node in a tree is NULL.
O(h)in average case if the tree is not skewed.