I managed to write an algorithm that, using recursion, allows me to go through all the elements of the tree and find the minimum value, but the main goal of the task is precisely to find the index of the minimum value (depth of the minimum node). Who can tell how to do this?

Here is the Node class code (element of the binary tree):

 сlass Node{ //vars Node left; Node right; int val; public Node(Node left, Node right, int val) { this.left = left; this.right = right; this.val = val; } //functions public Node getLeft() { return left; } public Node getRight() { return right; } public int getVal() { return val; } }

But the class in which the search for min. values:

 class App{ //vars static int min; static Node NODE; public static void main(String[] args) { //бинарное дерево в представлении объектов Node X = new Node(null,null,-12); Node I = new Node(null,X,-3); Node H = new Node(null,null,-700); Node G = new Node(null,null,-5); Node F = new Node(null,null,-10); Node D = new Node(H,I,-100); Node E = new Node(F,G,-2); Node C = new Node(E,D,3); Node B = new Node(null,null,1); Node A = new Node(B,C,6); NODE = A; min = A.getVal(); //min = 6 //поиск мин. значения calculateNode(A); } public static void calculateNode(Node node){ if(node.getLeft() != null) calculateLeftNode(node.getLeft()); if(node.getRight()!= null) calculateRightNode(node.getRight()); } public static void calculateLeftNode(Node node){ int value = node.getVal(); if(min > value) min = value; calculateNode(node); } public static void calculateRightNode(Node node){ int value = node.getVal(); if(min > value) min = value; calculateNode(node); } }

Here is a graphic representation of this tree: enter image description here

  • And under the index of the minimum value, what do you understand? - Pavel Parshin
  • @PavelParshin For example, the index of the desired number is 4 (starting from 1, not from 0). Well, the "right number" is an element of the tree H (-700) - SlandShow
  • That is the level / depth of the minimum node? - Pavel Parshin
  • @PavelParshin Yes. But the only problem is that I still can not figure out how to find it. I only have an idea with HashMap, but I don’t know if it will be released - SlandShow

1 answer 1

 static int minNodeLevel = -1; static int minValue = Integer.MAX_VALUE; public static void findMinNode(Node root) { calculateNode(root, 1); } private static void calculateNode(Node node, int nodeLevel) { if (node == null) { return; } int value = node.getVal(); if (minValue > value) { minValue = value; minNodeLevel = nodeLevel; } calculateNode(node.getLeft(), nodeLevel + 1); calculateNode(node.getRight(), nodeLevel + 1); }