LeetCode Q285: Inorder Successor in BST

Given a binary search tree and a node in it, find the in-order successor of that node in the BST.

Note: If the given node has no in-order successor in the tree, return null.

Solution:

Use stack to do in-order traversal.

	/**
	* Definition for a binary tree node.
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
	stack<TreeNode*> myStack;
	TreeNode* cur;
	myStack.push(root);
	cur = root->left;
	bool metP=false;
	while(cur!=NULL||!myStack.empty()){
	if(cur==NULL){
	TreeNode* node = myStack.top();
	myStack.pop();
	if(metP==true)
	return node;
	if(node == p)
	metP=true;
	cur = node->right;
	continue;
	}
	myStack.push(cur);
	cur=cur->left;
	}
	return NULL;
	}
	};

view raw Q285.cpp hosted with ❤ by GitHub

Round 2 solution:

	/**
	* Definition for a binary tree node.
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	TreeNode* InOrder(TreeNode* root, TreeNode* p, TreeNode*& lastAccessed){
	if(root==NULL)
	return NULL;
	TreeNode* l = InOrder(root->left, p, lastAccessed);
	if(lastAccessed==p){
	lastAccessed=root;
	return root;
	}
	lastAccessed=root;
	TreeNode* r = InOrder(root->right, p, lastAccessed);
	return l!=NULL? l:r!=NULL? r:NULL;
	}
	TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
	TreeNode* res=NULL;
	if(root==NULL||p==NULL)
	return NULL;
	TreeNode* lastAccessed=NULL;
	res = InOrder(root, p, lastAccessed);
	return res;
	}
	};

view raw Q285Rnd2.cpp hosted with ❤ by GitHub