I have the below question, but I'm having a hard time making sense of it and implementing it in PHP.
You have a binary tree with N nodes (1 <= N <= 100000) numbered from 0 to N - 1, each one labeled with some integer. You have to answer Q (1 <= Q <= 75000) queries, each one denoted by some node (some integer between 0 and N – 1).
The answer for each query is the largest difference between the labels you find in the path from the given node to the root of the tree, which will always be node 0. N will be given in the first line of the input. N lines follow the i-th line describes the data of the i-th node of the tree (the first line describes node 0, and so on), with 3 integers: label, left child, right child. The absence of any of the children will be denoted by -1. Then a line with the integer Q, followed by Q lines, each one a single query as described above.
Case 1:
For the input provided as follows:
3
10 1 2
12 -1 -1
15 -1 -1
2
1
2
The output of the program will be:
2
5
Case 2:
For the input provided as follows:
3
10 1 -1
15 2 -1
20 -1 -1
2
1
2
The output of the program will be:
5
10
Getting that maximum difference, for example for case 2,
I'd say output for query two would be 5 because from the data my binary tree has 10(root), then node 15 to the left of the root, then node 20 to the left of 15, so 20-15 is same as 15-10, which makes them both 5. Am I not understanding something here or what ... Any insights are welcome.