Search In A Binary Search Tree - Leetcode Solution

Here is a detailed solution for the "Search in a Binary Search Tree" problem on Leetcode:

Problem Statement: You are given the root of a binary search tree (BST) and an integer val. Find the node in the BST that the node's value equals val. If the node does not exist, return null.

Example 1: Input: root = [4,2,7,1,3], val = 2 Output: [2,1,3]

Example 2: Input: root = [4,2,7,1,3], val = 5 Output: []

Approach: The given tree is a binary search tree(BST). In BST, the value of the nodes in the left subtree is less than the value of the root and the value of the nodes in the right subtree is greater than the value of the root. Hence, we can traverse the tree to find the node whose value is equal to val.

We can start from the root of the tree and compare the value of the current node with val. If the current node value is equal to val, we return the current node. If the current node value is greater than val, we move to the left subtree to continue the search. If the current node value is less than val, we move to the right subtree to continue the search. We stop the search when we reach a leaf node or the node whose value is equal to val.

Algorithm:

1. Check if the root is null or the value of the root is equal to val, return the root.
2. If the value of the root is greater than val, recursively search in the left subtree.
3. If the value of the root is less than val, recursively search in the right subtree.
4. Return null if val is not found in the tree.

Code:

/**

• 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 searchBST(TreeNode* root, int val) { if (root == NULL || root->val == val) { return root; } if (root->val > val) { return searchBST(root->left, val); } else { return searchBST(root->right, val); } return NULL; } };

Time Complexity: O(h) where h is the height of the tree. Space Complexity: O(h) for the function call stack where h is the height of the tree.

Conclusion: In this problem, we learned how to search a node with a given value in a binary search tree. We used the property of the binary search tree to find the node in the tree. The time complexity of the solution is O(h) where h is the height of the tree.

1