Search in a Binary Search Tree
You are given the root of a binary tree. Find the node whose value is val and return that node, which means the whole subtree hanging below it. If no node has that value, return None. In a binary search tree every value in a left subtree is smaller than its node and every value in a right subtree is larger. All values are distinct.
Trees appear in the tests in level order, with null for a missing child, like [3,9,20,null,null,15,7]. Each node is a TreeNode with .val, .left and .right; the class is already defined for you.
Example 1
The node 2 has children 1 and 3, so the answer is the tree [2,1,3].
Example 2
5 is not in the tree: return None.
Constraints
0 <= number of nodes <= 100-1000 <= node.val <= 1000- The tree is a valid binary search tree.
-1000 <= val <= 1000
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Trees problems
- Smallest and Largest in a BSTBeginner
- Sum of All Node ValuesBeginner
- Total Nodes in a Binary TreeBeginner
- Univalued Binary TreeBeginner
- Values at Depth KBeginner
- Average of Levels in Binary TreeEasy
- Binary Tree Left Side ViewEasy
- Binary Tree Level Order TraversalEasy