Inorder Predecessor of Node in BST Editorial

Practice Problem Link: Inorder Predecessor of Node in BST

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

Problem Statement

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

Approach

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

• Traverse the given BST and if a node is found which is smaller than the node p and greater than the previously stored predecessor node then update the predecessor node.
• Return the predecessor 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* findPredecessor(Node* root, Node* p) {
    queue<Node*> treeNodes;
	treeNodes.push(root);
	Node* predecessor = NULL;
	while (!treeNodes.empty()) {
		Node* currentNode = treeNodes.front();
		treeNodes.pop();
		if (predecessor == NULL && currentNode->data < p->data) {
			predecessor = currentNode;
		}
		else if (predecessor != NULL && predecessor->data < currentNode->data && currentNode->data < p->data) {
			predecessor = currentNode;
		}
		if (currentNode->left != NULL) {
			treeNodes.push(currentNode->left);
		}
		if (currentNode->right != NULL) {
			treeNodes.push(currentNode->right);
		}
	}
	return predecessor;
}

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* predecessor;
void findNode(Node* root, Node* p) {
	if (root->left != NULL) {
		findNode(root->left, p);
	}
	if (predecessor == NULL && root->data < p->data) {
		predecessor = root;
	}
	else if (predecessor != NULL && predecessor.data < root->data && root->data < p->data) {
		predecessor = root;
	}
	if (root->right != NULL) {
		findNode(root->right, p);
	}
	return;
}
Node* findPredecessor(Node* root, Node* p) {
    predecessor = NULL;
	findNode (root, p);
	return predecessor;
}

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 findPredecessor(Node root, Node p) {
		Queue<Node> treeNodes = new LinkedList<Node> ();
		treeNodes.add(root);
		Node predecessor = null;
		while (!treeNodes.isEmpty()) {
			Node currentNode = treeNodes.peek();
			treeNodes.poll();
			if (predecessor == null && currentNode.data < p.data) {
				predecessor = currentNode;
			}
			else if (predecessor != null && predecessor.data < currentNode.data && currentNode.data < p.data) {
				predecessor = currentNode;
			}
			if (currentNode.left != null) {
				treeNodes.add(currentNode.left);
			}
			if (currentNode.right != null) {
				treeNodes.add(currentNode.right);
			}
		}
		return predecessor;
	}
}

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 predecessor;
	void findNode(Node root, Node p) {
		if (root.left != null) {
			findNode(root.left, p);
		}
		if (predecessor == null && root.data < p.data) {
			predecessor = root;
		}
		else if (predecessor != null && predecessor.data < root.data && root.data < p.data ) {
			predecessor = root;
		}
		if (root.right != null) {
			findNode(root.right, p);
		}
		return;
	}
	Node findPredecessor(Node root, Node p) {
	    predecessor = null;
		findNode (root, p);
		return predecessor;
	}
}