How to find the minimum value of a binary tree in JavaScript
A binary tree is a hierarchical data structure comprising nodes, with a maximum of two children per node: a left child and a right child. In a binary tree, the lowest value may be obtained by comparing values as we go through the tree until we find the smallest one.
In this Answer, we’ll look at how to do this in JavaScript in this Answer, along with a thorough explanation and a code sample.
Note: To learn about binary trees please see this Answer.
Understanding binary trees
Before getting into the code, let’s look at a binary tree’s structure. In a binary tree, every node possesses a value and two pointers, or references, to its left and right children. A tree-like structure is formed by each node with a maximum of two children, starting with the root node.
Here’s a simple representation of a binary tree:
Finding the minimum value
We can employ a recursive method to determine the lowest value in a binary tree. Starting at the root node, we can plan to visit each node as we navigate the tree. We’ll check each node’s value against the lowest value discovered so far. The minimum value is updated if the current node’s value is less. The left and right subtrees are then subjected to the same recursive procedure until the tree’s leaves are reached.
Code
Here is the implementation of this algorithm in JavaScript:
class TreeNode {constructor(value) {this.value = value;this.left = null;this.right = null;}}const findMinVal = (root) => {if (!root) {return Infinity;}const lMin = findMinVal(root.left);const rMin = findMinVal(root.right);return Math.min(root.val, lMin, rMin);}
Explanation
Lines 1–6: We define a
TreeNodeclass representing a binary tree node. Each node has three properties—value,leftandright—representing the node’s value and its left and right child, respectively. Theleftandrightproperties are set tonullinitially.Lines 8–17: We define a
findMinValfunction that recursively calls itself until it finds the minimum value in the tree. It starts by checking if the root is empty. Then, it moves toward the left and right sub-trees to find their minimum values by recursively calling the function. In the end, the function just finds the minimum value from the left and right sub-trees’ minimum values and the root node and returns it.
Non-recursive solution
We simulate the non-recursive solution by manually maintaining a stack of nodes to be visited, as opposed to employing recursive calls. Beginning at the tree’s root, the method iteratively pushes nodes onto the stack as it moves along the left subtree until it reaches the leftmost node. When it reaches a leaf node or a node without any left children, It checks the node’s value with the current minimum value and updates the minimum if necessary. After that, the algorithm proceeds to the processed node’s right subtree until the whole tree is explored. We effectively imitate the recursive method without the drawbacks of the call stack by employing a stack to monitor nodes, finally locating the binary tree’s minimal value.
Conclusion
In conclusion, we have explored the problem of determining the minimum value in a binary tree and its solution in JavaScript. By grasping this basic idea, developers may establish the basis for more complex tree-related algorithms and problem-solving strategies. The recursive nature of the solution demonstrates the elegant and potent use of function calls to effectively explore complicated data structures.
