Hitachi Data Systems Interview Question Software Engineer / Developers
Country: United States
Interview Type: In-Person
public List<List<int>> PrintSameLevelNode(TreeNode root)
{
List<List<int>> result = new List<List<int>>();
if (root == null)
return result;
Queue<TreeNode> qn = new Queue<TreeNode>();
qn.Enqueue(root);
while (qn.Count != 0)
{
List<int> list = new List<int>();
int level = qn.Count();
for (int i = 0; i < level; i++)
{
TreeNode node = qn.Dequeue();
list.Add(node.Value);
if (node.Left != null)
{
qn.Enqueue(node.Left);
}
if (node.Right != null)
{
qn.Enqueue(node.Right);
}
}
result.Add(list);
}
return result;
}
}
You have to take 2 stacks for this.
We can use one stack for printing from left to right and other stack for printing from right to left.
The implementation does not return the list of list.. but you can modify a bit to return that.
For now, I am printing the elements as desired instead of returning list of list
public void levelOrderTraversal()
{
if(root==null)
{
System.out.println("Empty tree");
return;
}
Stack <Node> s1=new Stack<>();
Stack <Node> s2=new Stack<>();
s1.add(root);
while(!s1.isEmpty()||!s2.isEmpty())
{
while(!s1.isEmpty())
{
Node temp=s1.pop();
System.out.print(temp.info+" ");
if(temp.right!=null)
s2.push(temp.right);
if(temp.left!=null)
s2.push(temp.left);
}
System.out.println("");
while(!s2.isEmpty())
{
Node temp=s2.pop();
System.out.print(temp.info+" ");
if(temp.left!=null)
s1.push(temp.left);
if(temp.right!=null)
s1.push(temp.right);
}
System.out.println("");
}
}
This problem is also known as zigzag or spiral order traversal or a tree. You can simply do a BFS / Level Order Traversal and reverse the list depending on whether it's an odd or an even level. I present a Python solution here which returns lists of lists also.
from queue import Queue
def zigzagPrintTree(root):
q = Queue()
q.put(root)
curLevel = 0
res = []
while q.qsize():
tempList = []
for _ in range(0, q.qsize()):
curr = q.get()
tempList.append(curr.data)
if curr.left: q.put(curr.left)
if curr.right: q.put(curr.right)
if curLevel % 2 == 0:
res.append(tempList)
else:
res.append(tempList[::-1])
curLevel += 1
return res
This problem is also known as zigzag or spiral order traversal of a tree. You can simply do a BFS / level order traversal and reverse the level list depending on the level of the tree. I present a python solution down below which also returns Lists of Lists.
from queue import Queue
def zigzagPrintTree(root):
q = Queue()
q.put(root)
curLevel = 0
res = []
while q.qsize():
tempList = []
for _ in range(0, q.qsize()):
curr = q.get()
tempList.append(curr.data)
if curr.left: q.put(curr.left)
if curr.right: q.put(curr.right)
if curLevel % 2 == 0:
res.append(tempList)
else:
res.append(tempList[::-1])
curLevel += 1
return res
def store_by_level(value, depth, memo={})
memo[depth] ||= []
if depth == 0 || depth % 2 == 0
memo[depth].push(value)
else
memo[depth].shift(value)
end
memo
end
def level_wise_list(root)
memo = {}
queue = [[root, 0]] # [node, depth]
while !queue.empty?
current, depth = queue.shift
memo = store_by_level(current.value, depth, memo)
queue << [current.left, depth + 1] if current.left
queue << [current.right, depth + 1] if current.right
end
return memo.values
end
ArrayList<LinkedList<TreeNode>> createLevelLists(TreeNode root)
{
ArrayList<LinkedList<TreeNode>> results = new ArrayList<LinkedList<TreeNode>> ();
LinkedList<TreeNode> current = new LinkedList<TreeNode> ();
if(root != null)
current.add(root);
while(current.size()>0)
{
results.add(current);
LinkedList<TreeNode> parents = current;
current = new LinkedList<TreeNode> ();
for(TreeNode p : parents)
{
boolean isEvenLevel = results.size() % 2;
addAlternateLevel(p, current, isEvenLevel);
}
}
return results;
}
void addAlternateLevel(TreeNode p, LinkedList<TreeNode> current, boolean isEvenLevel)
{
boolean isLeftNull = p.left == null;
boolean isRightNull = p.right == null;
if(isEvenLevel)
{
if(!isLeftNull)
current.add(p.left);
if(!isRightNull)
current.add(p.right);
}
else
{
if(!isRightNull)
current.add(p.right);
if(!isLeftNull)
current.add(p.left);
}
}
public List<List<Integer>> makelist(BinaryTreeNode tree){
List<List<Integer>> lt = new ArrayList<List<Integer>>();
makeList(tree, lt, 0);
return lt;
}
public void makeList(BinaryTreeNode node, List<List<Integer>> lt, int level){
if (node == null){
return;
}
if (lt.size() <= level){
List<Integer> res = new ArrayList<Integer>();
res.add(node.value);
lt.add(res);
}
else{
if (level %2 ==0)
lt.get(level).add(node.value);
else
lt.get(level).add(0,node.value);
}
makeList(node.left, lt, level+1);
makeList(node.right, lt, level+1);
}
private static void BSF_toggle(MyNode node) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> internal = new ArrayList<>();
Queue<MyNode> queue = new LinkedList<>();
queue.add(node);
int count = 0;
int p = 1;
while(!queue.isEmpty()){
count++;
MyNode n = queue.poll();
if (n != null) {
if (n.left != null) {
queue.add(n.left);
} else {
queue.add(null);
}
if (n.right != null) {
queue.add(n.right);
} else {
queue.add(null);
}
internal.add(n.data);
}
if(count == Math.pow(2, p)-1){
if(p %2 ==1){
Collections.reverse(internal);
}
result.add(internal);
internal = new ArrayList<>();
p++;
}
}
System.out.println(result);
}
}
public List<List<int>> PrintSameLevelNode(TreeNode root)
{
List<List<int>> result = new List<List<int>>();
if (root == null)
return result;
Queue<TreeNode> qn = new Queue<TreeNode>();
qn.Enqueue(root);
while (qn.Count != 0)
{
List<int> list = new List<int>();
int level = qn.Count();
for (int i = 0; i < level; i++)
{
TreeNode node = qn.Dequeue();
list.Add(node.Value);
if (node.Left != null)
{
qn.Enqueue(node.Left);
}
if (node.Right != null)
{
qn.Enqueue(node.Right);
}
}
result.Add(list);
}
return result;
}
}
public List<List<int>> PrintSameLevelNode(TreeNode root)
{
List<List<int>> result = new List<List<int>>();
if (root == null)
return result;
Queue<TreeNode> qn = new Queue<TreeNode>();
qn.Enqueue(root);
while (qn.Count != 0)
{
List<int> list = new List<int>();
int level = qn.Count();
for (int i = 0; i < level; i++)
{
TreeNode node = qn.Dequeue();
list.Add(node.Value);
if (node.Left != null)
{
qn.Enqueue(node.Left);
}
if (node.Right != null)
{
qn.Enqueue(node.Right);
}
}
result.Add(list);
}
return result;
}
}
My Java Code
- Joe May 04, 2017public List<List<Integer>> getList(TreeNode root){ List<List<Integer>> result = new ArrayList<List<>(); if(root==null) return result; Queue<TreeNode> q = new LinkedList<>(); q.add(root); while(q.size()>0){ List<Integer> tempList = new ArrayList<>(); int qsize = q.size(); for(int i=0;i<qsize;i++){ ListNode temp = q.poll(); tempList.add(temp.val); if(temp.right!=null) q.add(temp.right); if(temp.left!=null) q.add(temp.left); } result.add(tempList); } return result; }