Jayesh Karli's Blog

Photo by niko photos on Unsplash

Search in a Binary Search Tree - LeetCode

Search in a Binary Search Tree - LeetCode. O(log n) solutions. Iterative and recursive

·

Binary Search Tree (BST) is an excellent data structure for search operations and this question is an excellent one to practice its basics.

BST Properties

• The left sub-tree will always have values less than the root.
• The right sub-tree will always have values greater than the root.

Iterative approach

The first step is just checking if the root node is null or if its value is equal to val. If that's the case we just return our root node because it satisfies our condition.

After that, we jump into our while loop and do the following

1. Check for the same base condition in every iteration.
2. If the current node's value is greater than val we move to the left subtree.
3. If the current node's value is lesser than val we move to the right subtree.

After we're out of the loop our node's value is either null or equal to val. So we simply return that node.

``````class Solution {
public TreeNode searchBST(TreeNode root, int val) {

if(root == null || root.val == val) return root;

while(root != null && root.val != val) {

root = root.val > val ? root.left : root.right;

}

return root;
}
}
``````

Recursive approach

We are performing the following three operations for a recursive solution -

1. Return the current node if its value is equal to val or null.
2. If val is greater than the value of the current node we go to the right subtree.
3. If val is lesser than the value of the current node we go to the left subtree.
``````class Solution {
public TreeNode searchBST(TreeNode root, int val) {

if(root == null || root.val == val) return root;

if(val > root.val)
return searchBST(root.right, val);
else
return searchBST(root.left, val);
}
}
``````