Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /**
- * Definition for a binary tree node.
- * public class TreeNode {
- * int val;
- * TreeNode left;
- * TreeNode right;
- * TreeNode(int x) { val = x; }
- * }
- */
- /*
- Iterative Solution
- Time Complexity: O(N) - If the tree is skewed it will visit all nodes.
- Space Complexity: O(1)
- N = Number of nodes in the binary search tree.
- */
- class Solution {
- public TreeNode searchBST(TreeNode root, int val) {
- // if (root == null) {
- // return null;
- // }
- TreeNode cur = root;
- while (cur != null) {
- if (cur.val == val) {
- return cur;
- }
- cur = cur.val < val ? cur.right : cur.left;
- }
- return cur;
- }
- }
- /*
- Recusrive Solution
- Time Complexity: O(N) - If the tree is skewed it will visit all nodes.
- Space Complexity: O(H)
- N = Number of nodes in the binary search tree.
- H = Height of tree. (Recursion Stack)
- */
- class Solution {
- public TreeNode searchBST(TreeNode root, int val) {
- if (root == null) {
- return null;
- }
- if (root.val == val) {
- return root;
- }
- return val < root.val ? searchBST(root.left, val) : searchBST(root.right, val);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement