Level Order Successor of node in BST

How can we find level order successor of a node in bst if parent pointer is given开发者_如何学C(with out using Queue ) ?

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.