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.

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:

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.

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);}

**Lines 1–6:**We define a`TreeNode`

class representing a binary tree node. Each node has three properties—`value`

,`left`

and`right`

—representing the node’s value and its left and right child, respectively. The`left`

and`right`

properties are set to`null`

initially.**Lines 8–17:**We define a`findMinVal`

function 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.

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.

Non-recursive solution

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.

Copyright ©2024 Educative, Inc. All rights reserved

TRENDING TOPICS