700.search-in-a-binary-search-tree.md

700. Search in a Binary Search Tree

// Recursive
fun searchBST(root: TreeNode?, `val`: Int): TreeNode? {
    return when {
        root == null -> null
        root.`val` == `val` -> root
        `val` > root.`val` -> searchBST(root.right, `val`)
        else -> searchBST(root.left, `val`)
    }
}

// Iterative
fun searchBST(root: TreeNode?, `val`: Int): TreeNode? {
    var node: TreeNode? = root
    while (node != null) {
        if (node.`val` == `val`) return node
        else if (`val` > node.`val`) node = node.right
        else node = node.left
    }
    return node
}

• Time Complexity: O(h) where h is the height of the tree, wost case O(n) for skewed tree.
• Space Complexity: O(h) for recursive and O(1) for iterative.