Left Side View of a Tree - Amazon Top Interview Questions
Problem Statement :
Given a binary tree root, return the leftmost node's value on each level of the tree. Constraints n ≤ 100,000 where n is the number of nodes in root Example 1 Input root = [0, [5, null, null], [2, null, [1, null, null]]] Output [0, 5, 1]
Solution :
Solution in C++ :
vector<int> solve(Tree* root) {
vector<int> res;
queue<Tree*> q;
q.push(root);
while (q.size() != 0) {
int size = q.size();
for (int i = 0; i < size; i++) {
Tree* top = q.front();
q.pop();
if (i == 0) res.push_back(top->val);
if (top->left != NULL) q.push(top->left);
if (top->right != NULL) q.push(top->right);
}
}
return res;
}
Solution in Java :
import java.util.*;
/**
* public class Tree {
* int val;
* Tree left;
* Tree right;
* }
*/
class Solution {
List<Integer> list = new ArrayList<>();
public int[] solve(Tree root) {
helper(root, 0);
// converts List<Integer> to int[] array
return list.stream().mapToInt(Integer::intValue).toArray();
}
private void helper(Tree root, int level) {
if (root != null) {
if (list.size() == level) {
list.add(root.val);
}
helper(root.left, level + 1);
helper(root.right, level + 1);
}
}
}
Solution in Python :
class Solution:
def solve(self, root):
self.hash_map = set()
self.output = []
self.traverse(root, 0)
return self.output
def traverse(self, node, level):
if not node:
return
if level not in self.hash_map:
self.hash_map.add(level)
self.output.append(node.val)
self.traverse(node.left, level + 1)
self.traverse(node.right, level + 1)
View More Similar Problems
Tree: Preorder Traversal
Complete the preorder function in the editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's preorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the preOrder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the tree's
View Solution →Tree: Postorder Traversal
Complete the postorder function in the editor below. It received 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's postorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the postorder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the
View Solution →Tree: Inorder Traversal
In this challenge, you are required to implement inorder traversal of a tree. Complete the inorder function in your editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's inorder traversal as a single line of space-separated values. Input Format Our hidden tester code passes the root node of a binary tree to your $inOrder* func
View Solution →Tree: Height of a Binary Tree
The height of a binary tree is the number of edges between the tree's root and its furthest leaf. For example, the following binary tree is of height : image Function Description Complete the getHeight or height function in the editor. It must return the height of a binary tree as an integer. getHeight or height has the following parameter(s): root: a reference to the root of a binary
View Solution →Tree : Top View
Given a pointer to the root of a binary tree, print the top view of the binary tree. The tree as seen from the top the nodes, is called the top view of the tree. For example : 1 \ 2 \ 5 / \ 3 6 \ 4 Top View : 1 -> 2 -> 5 -> 6 Complete the function topView and print the resulting values on a single line separated by space.
View Solution →Tree: Level Order Traversal
Given a pointer to the root of a binary tree, you need to print the level order traversal of this tree. In level-order traversal, nodes are visited level by level from left to right. Complete the function levelOrder and print the values in a single line separated by a space. For example: 1 \ 2 \ 5 / \ 3 6 \ 4 F
View Solution →