[Leetcode] 700번: Search in a Binary Search Tree

https://leetcode.com/problems/search-in-a-binary-search-tree/description/?envType=study-plan-v2&envId=leetcode-75

initial

So i thought you have to return a list of roots val, root lefts val and root rights val. But we should just return root, which returns the Subtree.

Another impt thing relates to bane of DFS - returning None. Notice I do recursively search root left and right but i dont return anything. You have to get the value of recursion like

val = self.recursion(root.left)
return val

//or
return self.recursion(root.left)

cuz just doing self.recursion(root.left) won't make our recursion function return anything.

class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if root is None:
            return None
        if root.val==val:
            print([root,val, root.left.val, root.right.val])
            return [root,val, root.left.val, root.right.val]
        elif root.left==None or root.right==None:
            return
        self.searchBST(root.left,val)
        self.searchBST(root.right,val)
        return None

solution

class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if root is None:
            return None
        if root.val==val:
            return root
        if val< root.val:
            return self.searchBST(root.left,val)
        else:
            return self.searchBST(root.right,val)

u can also completely do it iteratively by updating current node until it becomes null

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        while (root != null) {
            if (root.val == val) {
                return root;
            } else if (val < root.val) {
                root = root.left;
            } else {
                root = root.right;
            }
        }
        return null;
    }
}

revisited oct 29th

the impt thing is BST is sorted in left->root->right. So we can search iteratively where if current node's value (69) is bigger than what we are looking for (2), then we should look to the left.

class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        node = root
        while node:
            if node.val==val:
                return node
            elif node.val>val:
                node=node.left
            else:
                node=node.right
        return None

complexity

time and space are
if balanced is o log n
if skewed is o n