BSTSearch.java

amitsen01ei

Sep 24th, 2023

117

Never

Add comment

Not a member of Pastebin yet? Sign Up, it unlocks many cool features!

Java 1.35 KB | Source Code | 0 0

raw download clone embed print report

public class BSTSearch {
/**
*Finds the given value in the binary search tree. The TreeNode class is assumed as below:
* <pre>{@code
* public class TreeNode {
*
* int val;
*
* TreeNode left;
*
* TreeNode right;
* }
* }</pre>
*
* Time Complexity:
* The search in a balanced BST takes O(log n) time. However,
* in the worst-case scenario (i.e., the tree is a skewed tree),
* the time complexity can go up to O(n).
*
*
* Space Complexity:
* The space complexity is O(h), where h is the height of the tree.
* This is because of the call stack size in a recursive approach.
* Again, for a balanced BST, this will be O(log n), but for a skewed tree,
* it could go up to O(n).
*
* @param root node of the BST
* @param val to search
* @return subtree rooted with the val
* null if not found
*/
public TreeNode searchBST(TreeNode root, int val) {
if (root == null) return null;
if (root.val == val) return root;
if (root.val < val) {
return searchBST(root.right, val);
}
return searchBST(root.left, val);
}
}

Add Comment

Please, Sign In to add comment