LeetCode. Search in a Binary Search Tree

Problem:

Given the root node of a binary search tree (BST) and a value. You need to find the node in the BST that the node's value equals the given value. Return the subtree rooted with that node. If such node doesn't exist, you should return NULL.

For example, 

 

In the example above, if we want to search the value 5, since there is no node with value 5, we should return NULL.

Note that an empty tree is represented by NULL, therefore you would see the expected output (serialized tree format) as [], not null.

 

-Summary-

1. if value of the root is the number we are looking for, we return the root tree.

2. Otherwise, we traverse the tree.

(Binary search tree - Binary Search Tree (BST), all keys in the left subtree of a key must be smaller and all keys in the right subtree must be greater. So a Binary Search Tree by definition has distinct keys and duplicates in binary search tree are not allowed)

 

- if the root value is bigger than what we are looking for, then we move root tree to the left subtree.

- if the root value is smaller than what we are looking for, then we move root tree to the right subtree.

 

3. return None if we never found the number.

 

모든 문제에 대한 저작권은 LeetCode 회사에 있습니다. [Copyright © 2020 LeetCode]