We are in Beta and we are offering 50% off! Use code BETATESTER at checkout.
You can access a significantly larger sample of the platform's content for free by logging in with your Gmail account. Sign in now to explore.

Search in Binary Search Tree (Leetcode 700)

Data Structures and Algorithms Easy Seen in real interview

You are given the root of a binary search tree (BST) and an integer val. Find the node in the BST that the node’s value equals val and return the subtree rooted with that node. If such a node does not exist, return null.

Examples:

  • Input:
    4
   / \
  2   6
 / \ / \
1  3 5  7
  • Output: 2


  • Input:
    4
   / \
  2   6
 / \ / \
1  3 5  7
  • Output: None
We check whether the input value is larger than the current node’s valued. If it is, we go right; if it isn’t, we go left. If it is equal to the node value, we return the node.

from typing import Optional

# Definition for a binary tree node. 
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def search_BST(root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
    while root:
        if root.val == val:
            return root
        elif root.val < val:
            # go right
            root = root.right
        else:
            root = root.left
    return root

We can run an example as follows:

root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
root.right.left = TreeNode(5)
root.right.right = TreeNode(7)
search_BST(root,2).val
## 2

And another example:

search_BST(root,11) is None
## True


The time complexity of this solution is \(O(H)\), where \(H\) is the height of the tree. In a balanced binary search tree we would have had \(O(logn)\), since \(H = log(n)\). However, the worst case scanrio (one-way sided tree) time complexity will be \(O(N)\).


Topics

Binary Search, Binary Search Tree
Similar questions

Provide feedback