[Google] Postorder successor in Binary Tree

Question

link

Write an algorithm to find the ‘next’ post-order successor of a given node in a binary tree and binary search tree.

1. where each node has a link to its parent.
2. without parent pointer

Implement 2 versions of the algorithm: 1.) binary tree 2.) BST

Solution

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).