If you're interested in becoming a Full Stack Developer without a degree, we've put together some tips and resources to help you get started. Learn the Fundamentals The first step to becoming a Full Stack Developer is to learn the fundamentals of coding. You can start with HTML, CSS, and JavaScript, which are the building blocks of web development. There are plenty of free resources available online, such as Codecademy and FreeCodeCamp, which offer interactive courses that teach you the basics of web development. Once you have a solid understanding of the basics, you can move on to more advanced topics such as back-end development, databases, and frameworks. You can learn these topics through online courses or by working on personal projects. Build a Portfolio One of the most important things you can do as a Full Stack Developer is to build a portfolio. Your portfolio should showcase your skills and experience and demonstrate your ability to build real-world applications. You c
Problem Statement:(👈click here for GFG)
Given a Binary Tree, find its Boundary Traversal. The traversal should be in the following order:
- Left boundary nodes: defined as the path from the root to the left-most node ie- the leaf node you could reach when you always travel preferring the left subtree over the right subtree.
- Leaf nodes: All the leaf nodes except for the ones that are part of left or right boundary.
- Reverse right boundary nodes: defined as the path from the right-most node to the root. The right-most node is the leaf node you could reach when you always travel preferring the right subtree over the left subtree. Exclude the root from this as it was already included in the traversal of left boundary nodes.
Note: If the root doesn't have a left subtree or right subtree, then the root itself is the left or right boundary.
Example 1:
Input: 1 / \ 2 3 / \ / \ 4 5 6 7 / \ 8 9 Output: 1 2 4 8 9 6 7 3 Explanation:
Example 2:
Input: 1 / 2 / \ 4 9 / \ \ 6 5 3 / \ 7 8 Output: 1 2 4 6 5 7 8 Explanation: As you can see we have not taken the right subtree.
Your Task:
This is a function problem. You don't have to take input. Just complete the function boundary() that takes the root node as input and returns an array containing the boundary values in anti-clockwise.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(Height of the Tree).
Constraints:
1 ≤ Number of nodes ≤ 10^5
1 ≤ Data of a node ≤ 10^5
Solution:
class Solution {
boundary(root) {
let result = [];
if (!root) {
return result;
}
result.push(root.data);
// Add left boundary
let curr = root.left;
while (curr) {
if (curr.left || curr.right) {
result.push(curr.data);
}
if (curr.left) {
curr = curr.left;
} else {
curr = curr.right;
}
}
// Add leaf nodes
this.getLeafNodes(root, result);
// Add right boundary
let stack = [];
curr = root.right;
while (curr) {
if (curr.left || curr.right) {
stack.push(curr.data);
}
if (curr.right) {
curr = curr.right;
} else {
curr = curr.left;
}
}
while (stack.length) {
result.push(stack.pop());
}
// Remove duplicates if root is leaf node
if (result.length > 1 && root.left == null && root.right == null) {
result.splice(result.length - 1, 1);
}
return result;
}
// Helper function to get all leaf nodes
getLeafNodes(node, result) {
if (!node) {
return;
}
if (!node.left && !node.right) {
result.push(node.data);
return;
}
this.getLeafNodes(node.left, result);
this.getLeafNodes(node.right, result);
}
}
Comments
Post a Comment