Inorder Successor of Node in BST Editorial

Practice Problem Link: Inorder Successor of Node in BST

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

The inorder successor of a node p is the node q that comes just after p in the binary tree's inorder traversal. Given the root node of a binary search tree and the node p, find the inorder successor of node p. If it does not exist, return null.

Approach

The inorder successor can be found by simply traversing the BST. 

• Traverse the given BST and if a node is found which is greater than the node p and smaller than the previously stored successor node then update the successor node.
• Return the successor node as the answer.

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(n)

Implementation

C++ (BFS)

/* This is the Node class definition

class Node {
public:
    Node* left;
    Node* right;
    int data;

    Node(int data) {
        this->left = NULL;
        this->right = NULL;
        this->data = data;
    }
};
*/

Node* findSuccessor(Node* root, Node* p) {
    queue<Node*> treeNodes;
	treeNodes.push(root);
	Node* successor = NULL;
	while (!treeNodes.empty()) {
		Node* currentNode = treeNodes.front();
		treeNodes.pop();
		if (successor == NULL && currentNode->data > p->data) {
			successor = currentNode;
		}
		else if (successor != NULL && successor->data > currentNode->data && currentNode->data > p->data) {
			successor = currentNode;
		}
		if (currentNode->left != NULL) {
			treeNodes.push(currentNode->left);
		}
		if (currentNode->right != NULL) {
			treeNodes.push(currentNode->right);
		}
	}
	return successor;
}

C++ (DFS)

/* This is the Node class definition

class Node {
public:
    Node* left;
    Node* right;
    int data;

    Node(int data) {
        this->left = NULL;
        this->right = NULL;
        this->data = data;
    }
};
*/
Node* successor;
void findNode (Node* root, Node* p) {
	if (root->left != NULL) {
		findNode(root->left, p);
	}
	if (successor == NULL && root->data > p->data) {
		successor = root;
	}
	else if(successor != NULL && root->data > p->data && root->data < successor->data) {
		successor = root;
	}
	if (root->right != NULL) {
		findNode(root->right, p);
	}
	return;
}
Node* findSuccessor(Node* root, Node* p) {
    successor = NULL;
	findNode(root, p);
	return successor;
}

Java (BFS)

class Solution {
	/* This is the Node class definition
	
	class Node {
		public Node left;
		public Node right;
		public int data;

		public Node(int data) {
			this.data = data;
		}
	}
	*/

	Node findSuccessor(Node root, Node p) {
	    Queue<Node> treeNodes = new LinkedList<Node> ();
		treeNodes.add(root);
		Node successor = null;
		while (!treeNodes.isEmpty()) {
			Node currentNode = treeNodes.peek();
			treeNodes.poll();
			if (successor == null && currentNode.data > p.data) {
				successor = currentNode;
			}
			else if (successor != null && successor.data > currentNode.data && currentNode.data > p.data) {
				successor = currentNode;
			}
			if (currentNode.left != null) {
				treeNodes.add(currentNode.left);
			}
			if (currentNode.right != null) {
				treeNodes.add(currentNode.right);
			}
		}
		return successor;
	}
}

Java (DFS)

class Solution {
	/* This is the Node class definition
	
	class Node {
		public Node left;
		public Node right;
		public int data;

		public Node(int data) {
			this.data = data;
		}
	}
	*/
	Node successor;
	void findNode (Node root, Node p) {
		if (root.left != null) {
			findNode(root.left, p);
		}
		if (successor == null && root.data > p.data) {
			successor = root;
		}
		else if(successor != null && root.data > p.data && root.data < successor.data) {
			successor = root;
		}
		if (root.right != null) {
			findNode(root.right, p);
		}
		return;
	}
	Node findSuccessor(Node root, Node p) {
	    successor = null;
		findNode (root, p);
		return successor;
	}
}