Search in a Binary Search Tree (BST) Editorial

Practice Problem Link: Search in a Binary Search Tree (BST)

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

Problem Statement

Given the root node of a binary search tree and a key, return the subtree rooted at the node containing the key. If it does not exist, return null.

Note: The tree contains only unique values.

Approach

Traverse the given BST recursively and for each node:

• If the node is equal to the key then return the node.
• If the node is greater than the key then the key must be in the left subtree. Recursively call the left subtree.
• If the node is smaller than the key then the key must be in the right subtree. Recursively call the right subtree.

Analysis

• Time Complexity: O(Height of BST)
• Auxiliary Space Complexity: O(1)

Implementation

C++ 

/* 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* searchBst(Node* root, int key) {
    if (root->data == key) {
		return root;
	}
	if (root->data > key && root->left != NULL) {
		return searchBst(root->left, key);
	}
	if (root->data < key && root->right != NULL) {
		return searchBst(root->right, key);
	}
	return NULL;
}

Java

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 searchBst(Node root, int key) {
	    if (root.data == key) {
			return root;
		}
		if (root.data > key && root.left != null) {
			return searchBst(root.left, key);
		}
		if (root.data < key && root.right != null) {
			return searchBst(root.right, key);
		}
		return null;
	}
}