How can we find level order successor of a node in bst if parent pointer is given(with out using Queue ) ?
A:
In the basic case, it's the right sibling of node. Otherwise you need to wraparound to the next level, or return No successor.
Go up to the next parent with a right child, and traverse it left back down to level of node. If you're able to trace back to root with no right children, go down the left side to level + 1. If you reach an empty child ptr, return no successor.
If it's not a full BST, you may need to do a little more work - repeating until you find a node at the desired level.
Stephen
2010-05-04 10:42:15
It's fine.But I'm still thinking to do it in O(n) time and O(1) space
dsiap
2010-05-04 10:47:48
@dslap : this solution is O(n) time, O(1) space.
Stephen
2010-05-04 11:10:29
213 4 5 6 7Here your algorithm has to return 7 for LOS(6) .Will it do ?There are so much cases to be considered like this
dsiap
2010-05-04 12:33:21