332. Smallest Value in a Search Tree
Foundation1000 ms256 MBSolved by 0%
The tree is a binary search tree. Print its smallest value.
Do not search the whole tree. In a search tree everything smaller than a node lives in its left subtree, so the smallest value is at the end of the leftmost path. Walk left until there is no left child, and that node holds it.
That is a handful of steps rather than a full traversal, and it is the reason finding a minimum in a search tree is cheap.
Constraints - `1 ≤ n ≤ 100000` - `-1000000000 ≤ value ≤ 1000000000` - All values are distinct and the tree is a valid search tree.
Input
The first line contains an integer n, the number of nodes.
The second line contains n values, where node i holds the ith value.
Each of the next n lines contains two integers, the left and right child of
node i, using 0 for no child. Node 1 is the root.
Output
Print one integer, the smallest value in the tree.
Input7
4 2 6 1 3 5 7
2 3
4 5
6 7
0 0
0 0
0 0
0 0
Output1
Notehas its smallest value two steps down the left path
Input1
7
0 0
Output7
Noteis a single node, which is its own minimum
Hint 1Approach
Hint 2Approach
Hint 3Pseudocode
Hint 4Full solution