Search Path in a BST
You are given the root of a binary tree. Search the BST for x the usual way: start at the root, go left if x is smaller than the node and right if it is larger, and stop when you reach a node holding x or run off the tree. Return the list of values of the nodes you visited, in order, including the matching node if there is one. An empty tree gives []. 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.
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
Visit 8, then 3, then 6 (found).
Example 2
Visit 8, 3, 6, then 7 would be the right child of 6, which is missing.
Constraints
0 <= number of nodes <= 100-1000 <= node.val <= 1000- The tree is a valid binary search tree.
-1000 <= x <= 1000
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Trees problems
- Search in a Binary Search TreeBeginner
- 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