Write an algorithm to find the ‘next’ post-order successor of a given node in a binary tree and binary search tree.
- where each node has a link to its parent.
- without parent pointer
Implement 2 versions of the algorithm: 1.) binary tree 2.) BST
In postorder, any node below current node shall be ‘predecessor’ of current node. Thus we only care about current node’s parent.
Suggested by a user:
1) parent pointer is given. - go to the parent of the current node. - if current node is the right child of its parent => print parent. - else return leftmost node of the right sub-tree of parent. 2) parent pointer is not given. - traverse the tree and find the parent of the current node - do the same as method (1).