Find the inorder predecessor and successor of a given key in a binary search tree. | Hello World
1. If the node has a left chlid then we find the right most child in the left subtree. In the above example node 10's predecessor is 7
2. If the node does not have a left child, if it is the right child of its parent, then its parent will be the predecessor.
3. If the node does not have a left child and it is the left child of its parent. Then we need to follow up the tree until we find a node that is a right child of its parent. In the above example, node 11's predecessor is 10.
The in-order successor is basically the same.
Read full article from Find the inorder predecessor and successor of a given key in a binary search tree. | Hello World
No comments:
Post a Comment