A binary search tree, or BST for short, is a tree whose nodes each store a key greater than all their left child nodes and less than all of their right child nodes. There must be no duplicate nodes.

Binary trees are useful for storing data in an organized way, which allows for it to be fetched, inserted, updated, and deleted quickly. The greater-than and less-than ordering of nodes mean that each comparison skips about half of the remaining tree, so the whole lookup takes time proportional to the number of nodes in the tree.

Given a binary search tree and a search target N, find out the node in the tree has the same value as N. Return the target node and None if not found.

Sample Input:

root = [ 6, 3, 9, 2, 4, 7, 10], N = 3

Sample Output:

<3, <2, None, None>, <4, None, None>>

数据结构和算法：初级练习题 #38 – 二叉搜索树

二叉搜索树是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉搜索树。

二叉搜索树作为一种经典的数据结构，它既有链表的快速插入与删除操作的特点，又有数组快速查找的优势；所以应用十分广泛，例如在文件系统和数据库系统一般会采用这种数据结构进行高效率的排序与检索操作。

给定一颗二叉搜索树和一个搜索数N，在这颗树里找到包含数字N的结点。如果不存在则返回空。

输入样例：

root = [ 6, 3, 9, 2, 4, 7, 10], N = 3

输出样例：

<3, <2, None, None>, <4, None, None>>

Python Solution