Problem

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

Consider the tree:

1
2
3
4
5

       4
     /   \
   2      7
 /   \
1     3

Example 1:

1
2
3

Input:
root = [4,2,7,1,3], val = 2
Output: [2,1,3]

Example 2:

1
2

Input: root = [4,2,7,1,3], val = 5
Output: []

Solution

Method 1 - Recursive

searchBST(TreeNode root, int val) : Its very simple operation to perform.

  1. Start at the root of the BST.
  2. If the current node’s value equals val, return the current node.
  3. If val is less than the current node’s value, move to the left child.
  4. Otherwise, move to the right child.
  5. If during traversal no node is found, return null.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null || root.val == val) {
            return root; // Base case: node is found or does not exist
        }
        if (val < root.val) {
            return searchBST(root.left, val); // Search in the left subtree
        } else {
            return searchBST(root.right, val); // Search in the right subtree
        }
    }
}
1
2
3
4
5
6
7
8

class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if not root or root.val == val:
            return root # Base case: node is found or does not exist
        if val < root.val:
            return self.searchBST(root.left, val) # Search in the left subtree
        else:
            return self.searchBST(root.right, val) # Search in the right subtree

Complexity

  • ⏰ Time complexity: O(h). The time complexity of search and insertion operations in a Binary Search Tree (BST) is O(h), where h represents the tree’s height. In the worst-case scenario, traversal may occur from the root to the deepest leaf node, and for a skewed tree, the height becomes n, resulting in a time complexity of O(n).
    • Balanced BST: O(log(n))
    • Skewed BST: O(n)
    • While searching in BSTs is generally faster than linked lists, this efficiency depends significantly on the tree’s structure. If all inserted items are greater and form only right subtrees, the BST becomes similar to a linked list, leading to slow search operations with worst-case complexity of O(n).
---
title: Insert [1,2,3,4,5,6]
---

graph TD;
	A(1) ~~~ N1:::hidden
	A --- B(2)
	B ~~~ N2:::hidden
	B --- C(3)
	C ~~~ N3:::hidden
	C --- D(4)
	D ~~~ N4:::hidden
	D --- E(5)
	E ~~~ N5:::hidden
	E --- F(6)
				
G

classDef hidden display:none
G@{ shape: comment, label: "Is it a tree or linked list?" }

  • In contrast, a balanced BST enables much faster searching with a time complexity of O(log(n)).

  • 🧺 Space complexity: O(h). - Space is consumed by the function call stack during recursion.

    • Balanced BST: O(log(n))
    • Skewed BST: O(n)

By inserting only greater items there are only right sub-trees – the tree isn’t different from a linked list and the searching is slow! That makes the worst-case searching as slow as on linked list which is linear O(n). However if the tree is somehow balanced we can search very quickly with O(log(n)) time.

Further Optimization

Binary search trees can become inefficient, so it is crucial to ensure they remain balanced for faster search operations. This can be achieved by maintaining a balanced binary search tree during insertion. A balanced tree is a data structure in which the height difference between the left and right subtrees is at most one level.

Searching in a balanced tree is significantly faster than in some binary search trees!

Method 2 - Iterative

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        while (root != null) {
            if (root.val == val) {
                return root; // Found the node
            } else if (val < root.val) {
                root = root.left; // Move to the left subtree
            } else {
                root = root.right; // Move to the right subtree
            }
        }
        return null; // Node not found
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        while root:
            if root.val == val:
                return root # Found the node
            elif val < root.val:
                root = root.left # Move to the left subtree
            else:
                root = root.right # Move to the right subtree
        return None # Node not found

Complexity

  • ⏰ Time complexity: O(log n) in case tree is balanced.
    • The maximum number of nodes visited is proportional to the height of the tree.
    • In a balanced BST, the height is approximately log(n), so the time complexity is O(log(n)).
    • In the worst case (skewed tree), the height can be up to n, so the complexity is O(n).
  • 🧺 Space complexity: O(1). The iterative solution has O(1) space complexity since no additional space for recursion is used.