Amazon Interview Question
SDE-2sCountry: United States
class Node:
def __init__(self, key=None, left=None, right=None):
self.key = key
self.left = left
self.right = right
def printLevel(root, level):
# base case
if root is None:
return False
if level == 1:
print(root.key, end=' ')
return True
left = printLevel(root.left, level - 1)
right = printLevel(root.right, level - 1)
return left or right
def levelOrderTraversal(root):
level = 1
while printLevel(root, level):
level = level + 1
if __name__ == '__main__':
root = Node(15)
root.left = Node(10)
root.right = Node(20)
root.left.left = Node(8)
root.left.right = Node(12)
root.right.left = Node(16)
root.right.right = Node(25)
levelOrderTraversal(root)
class Node:
def __init__(self, key=None, left=None, right=None):
self.key = key
self.left = left
self.right = right
def printLevel(root, level):
if root is None:
return False
if level == 1:
print(root.key, end=' ')
return True
left = printLevel(root.left, level - 1)
right = printLevel(root.right, level - 1)
return left or right
def levelOrderTraversal(root):
level = 1
while printLevel(root, level):
level = level + 1
if __name__ == '__main__':
root = Node(15)
root.left = Node(10)
root.right = Node(20)
root.left.left = Node(8)
root.left.right = Node(12)
root.right.left = Node(16)
root.right.right = Node(25)
levelOrderTraversal(root)
level order using dfs
recursive : recursively call left child first and right child next while adding visited nodes to result.
time O(n)
space O(n)
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
levelOrderUtil(root, 0, result);
return result;
}
private static void levelOrderUtil(TreeNode node, int level, List<List<Integer>> result) {
if (node == null) {
return;
}
if (result.size() < level + 1) {
result.add(new LinkedList<Integer>());
}
result.get(level).add(node.val);
levelOrderUtil(node.left, level + 1, result);
levelOrderUtil(node.right, level + 1, result);
return;
}
}
/*
iterative : use a stack
time O(n)
space O(n)
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
levelOrderUtil(root, result);
return result;
}
private void levelOrderUtil(TreeNode node, List<List<Integer>> result) {
if (node == null) {
return;
}
Stack<Node> s = new Stack<>();
Node temp = new Node(node, 0);
s.push(temp);
while (!s.empty()) {
temp = s.pop();
if (result.size() < temp.level + 1) {
result.add(new LinkedList<Integer>());
}
result.get(temp.level).add(temp.tn.val);
if (temp.tn.right != null) {
s.push(new Node(temp.tn.right, temp.level + 1));
}
if (temp.tn.left != null) {
s.push(new Node(temp.tn.left, temp.level + 1));
}
}
return;
}
class Node {
TreeNode tn;
int level;
public Node(TreeNode tn, int level) {
this.tn = tn;
this.level = level;
}
}
}
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
levelHelper(res, root, 0);
return res;
}
public void levelHelper(List<List<Integer>> res, TreeNode root, int height) {
if (root == null) return;
if (height >= res.size()) {
res.add(new LinkedList<Integer>());
}
res.get(height).add(root.val);
levelHelper(res, root.left, height+1);
levelHelper(res, root.right, height+1);
}
- prathap July 25, 2020