700. Search in a Binary Search Tree #

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.

Example 1:

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

Example 2:

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

Constraints:

• The number of nodes in the tree is in the range [1, 5000].
• 1 <= Node.val <= 10000000
• root is a binary search tree.
• 1 <= val <= 10000000

Summary #

Given the root node of a binary search tree (BST) and a value. You need to find the node in the BST whose node value equals the given value. Return the subtree rooted at that node. If the node does not exist, return NULL.

Solution Approach #

• According to the properties of a binary search tree (the value of the root node is greater than the values of all nodes in the left subtree and less than the values of all nodes in the right subtree), solve recursively

Code #

package leetcode

import (
	"github.com/halfrost/leetcode-go/structures"
)

// TreeNode define
type TreeNode = structures.TreeNode

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func searchBST(root *TreeNode, val int) *TreeNode {
	if root == nil {
		return nil
	}
	if root.Val == val {
		return root
	} else if root.Val < val {
		return searchBST(root.Right, val)
	} else {
		return searchBST(root.Left, val)
	}
}