Return the Leftmost Value in the Last Row of the Binary Tree using JavaScript
Given the root of a binary tree, our task is to return the leftmost value in the last row of the binary tree in JavaScript. Here we use recursive and iterative approaches to return the leftmost value in the last row.
Explanation: The image below illustrates the leftmost value in the last row of the binary tree is 7.
Binary Tree
Below are the approaches to return the leftmost value in the last row of the binary tree using JavaScript:
Table of Content
- Recursive Approach
- Iterative Approach
Recursive Approach
The code defines a Node class to represent nodes in a binary tree and initializes variables for tracking the maximum level, root node, and result. It utilizes a recursive function ‘deepestLeftLeafUtil’ to traverse the tree, identifying the leftmost leaf node in the last row based on the depth. A binary tree is constructed, and the deepestLeftLeaf function is called to find the leftmost leaf node. If found, its data value is printed otherwise a message indicating no left leaf in the tree is printed.
Example: The example below shows how to return the leftmost value in the last row of the binary tree using the Recursive Approach.
class Node {
constructor(data) {
this.left = null;
this.right = null;
this.data = data;
}
}
let maxlevel = 0;
let root;
let result;
function deepestLeftLeafUtil(node, lvl, isLeft) {
// Base case
if (node == null)
return;
if (isLeft != false &&
node.left == null &&
node.right == null &&
lvl > maxlevel) {
result = node;
maxlevel = lvl;
}
deepestLeftLeafUtil(node.left, lvl + 1, true);
deepestLeftLeafUtil(node.right, lvl + 1, false);
}
// A wrapper over deepestLeftLeafUtil()
function deepestLeftLeaf(node) {
deepestLeftLeafUtil(node, 0, false);
}
// Driver code
root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.right.left = new Node(5);
root.right.right = new Node(6);
root.right.left.left = new Node(7);
deepestLeftLeaf(root);
if (result != null)
console.log(result.data);
else
console.log("There is no left leaf in the given tree");
Output
7
Time Complexity: O(n), where n is the number of nodes in a given binary tree.
Space Complexity: O(n).
Iterative Approach(Using Level Order Traversal)
In this approach, a ‘Node’ class represents nodes in a binary tree and provides a utility function ‘newNode’ to create new nodes. The ‘deepestLeftLeaf’ function iterates through the tree level by level using a queue, tracking the leftmost node encountered at each level. It returns the leftmost leaf node found in the last row. A binary tree is constructed, and the “deepestLeftLeaf” function is called to find the leftmost leaf node in the last row. If found, its data value is printed otherwise a message indicates that there is no left leaf in the tree.
Example: The example below shows return the leftmost value in the last row of the binary tree in JavaScript using Iterative Approach.
class Node {
constructor(data) {
this.data = data;
this.left = null;
this.right = null;
}
}
function newNode(data) {
return new Node(data);
}
function deepestLeftLeaf(root) {
if (root == null) return null;
let ans = null;
let q = [];
q.push(root);
while (q.length > 0) {
let front_node = q.shift();
if (front_node.left) {
q.push(front_node.left);
ans = front_node.left;
}
if (front_node.right) q.push(front_node.right);
}
return ans;
}
let root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.right.left = new Node(5);
root.right.right = new Node(6);
root.right.left.left = new Node(7);
let result = deepestLeftLeaf(root);
if (result)
console.log(result.data);
else
console.log("There is no left leaf in the given tree.");
Output
7
Time Complexity: O(n), where n is the number of nodes in given binary tree.
Space Complexity: O(n) .
Contact Us