Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
Well, BFS its when we using queue - we go through all nodes on the first level, then through all nodes on the second level etc
When we use stack situation is different. Using stack is the same as using recursive function. It will work just as DFS:
{
Stack nodes = new Stack();
Stack levels = new Stack();
stack.push(root);
levels.push(0);
int maxLevel = 0;
while(!stack.isEmpty()) {
Node currentNode = stack.pop();
int currentLevel = levels.pop();
if(currentLevel > maxLevel) {
maxLevel = currentLevel;
}
if(currentNode.getRightChild() != null) {
stack.push(currentNode.getRightChild());
}
if(currentNode.getLeftChild() != null) {
stack.push(currentNode.getLeftChild());
}
}
return maxLevel;
}
To ensure that it works just like DFS assume we have such tree
1
/ \
2 3
/ \ / \
4 5 6 7
then procedure acts like this:
1) adds 1 to the stack
2) pops 1 from the stack, pushes 3 to the stack then pushes 2 to the stack, 2 is in the head
3) pops 2 from the stack, pushes 5 to the stack then pushes 4 to the stack
4) pops 4 and pushes nothing
5) pops 5 and pushes nothing
6) pops 3, pushes 7 and 6
7) pops 6 and 7 and that's it
so the route is like 1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7
just like in the BSF.
Cheers!
Oh, sorry, I forgot to update levels on each step, so we should change this
if(currentNode.getRightChild() != null) {
stack.push(currentNode.getRightChild());
}
if(currentNode.getRightChild() != null) {
stack.push(currentNode.getRightChild());
}
to this:
if(currentNode.getRightChild() != null) {
stack.push(currentNode.getRightChild());
levels.push(currentLevel + 1);
}
if(currentNode.getRightChild() != null) {
stack.push(currentNode.getRightChild());
levels.push(currentLevel + 1);
}
So much code why?????
//With recursion
int findHeight(Node n)
{
if(n==null)
return 0;
int maxH=0;
for(Node n=n.child.head; n; n=n.next)
MAX(maxH,findHeight(n));
return maxH+1;
}
now if can't use the run time stack (why you would ever do that I do not know...
class StackFrame
{
public:
int height;
node n;
StackFrame(Node n, int h){this.n=n; height=h;}
}
int findHeight(Node n)
{
if(n==null)
return 0;
Stack<StackFrame> frames=new Stack<StackFrame>;
int maxH=0;
frames.push(new StackFrame(n, 1));
while(frames.size()>0)
{
StackFrame f=frames.pop();
maxH=MAX(maxH,f.height);
for(Node c : f.children) //assume public children list
frames.push(c, f.height+1);
}
return maxH;
}
This question is basically asking for iterative version of DFS or more specifically Postorder (which is also a DFS). So idea is do a iterative postorder using stack(one or two stack, depends you want complicated or simple solution) and then keep track of the size of stack.
For this question, you want to use DFS using post order traversal - that is visit left, right and self.
To calculate the height, the stack will always represent a *single* path of the tree. Therefore, during the self node valuation, just take the maximum of current stack size and the max thus far.
public int getHeight(Node node) {
if (node == null)
return -1;
int max = -1;
Stack<Node> stack = new Stack<Node>();
stack.add(node);
while (!stack.isEmpty()) {
Node current = stack.peek();
if (current.left != null) {
stack.add(current.left);
continue;
}
if (current.right != null) {
stack.add(current.right);
continue;
}
max = Math.max(max, stack.size() - 1);
stack.pop();
}
return max;
}
For the N-ary tree, it's bit tricky. You want to use the same strategy for the BST DFS, however since there is N number of children, you must keep track of the nodes that's visited or keep an index on each children node that you're processing.
public int height(GraphNode node) {
Set<GraphNode> visitedNodeSet = new HashSet<>();
Stack<GraphNode> stack = new Stack<GraphNode>();
int max = -1;
if (node == null)
return max;
while (!stack.isEmpty()) {
GraphNode currentNode = stack.peek();
for (GraphNode childNode : currentNode.children()) {
if (!visitedNodeSet.contains(childNode)) {
stack.add(childNode);
visitedNodeSet.add(childNode);
continue;
}
}
max = Math.max(max, stack.height() - 1);
stack.pop();
}
return max;
}
On a side note, it's pretty terrible they asked to use a stack. It's so much less code to do it recursively.
package binarytree;
import java.util.ArrayDeque;
import java.util.Deque;
import org.junit.Assert;
import org.junit.Test;
public class BinaryTreeHeightNonRecursive {
/**
* Calculates height for binary tree using stack
*
* @param root
* the root node of binary tree
* @return height of tree
*/
public int height(Node<Integer> root) {
if (root == null)
return 0;
Deque<NodeWrapper<Integer>> stack = new ArrayDeque<>();
int height = 0;
NodeWrapper<Integer> wrapper = new NodeWrapper<>(root, height);
stack.push(wrapper);
while (!stack.isEmpty()) {
NodeWrapper<Integer> current = stack.pop();
if (height < current.height) {
height = current.height;
}
Node<Integer> left = current.node.left;
if (left != null) {
wrapper = new NodeWrapper<>(left, current.height + 1);
stack.push(wrapper);
}
Node<Integer> right = current.node.right;
if (right != null) {
wrapper = new NodeWrapper<>(right, current.height + 1);
stack.push(wrapper);
}
}
return height;
}
@Test
public void testHeight() {
Node<Integer> node = new Node<>(10);
node.left = new Node<>(8);
node.right = new Node<>(13);
node.left.left = new Node<>(5);
node.left.right = new Node<>(9);
node.right.right = new Node<>(17);
node.right.right.right = new Node<>(19);
int height = height(node);
Assert.assertEquals(3, height);
}
/**
* Wrapper class for Node to keep height
*
* @param <T>
*/
public class NodeWrapper<T> {
Node<T> node;
int height;
public NodeWrapper(Node<T> node, int height) {
this.node = node;
this.height = height;
}
}
/**
* Wrapper class for BTreeNode to keep height
*
* @param <T>
*/
public class BTreeNodeWrapper<T> {
BTreeNode<T> node;
int height;
public BTreeNodeWrapper(BTreeNode<T> node, int height) {
this.node = node;
this.height = height;
}
}
/**
* Calculates height for n-ary tree using stack
*
* BTree is used for an example
*
* @param root
* the root node of BTree
* @return height of tree
*/
public int height(BTreeNode<Integer> root) {
if (root == null)
return 0;
Deque<BTreeNodeWrapper<Integer>> stack = new ArrayDeque<>();
int height = 0;
BTreeNodeWrapper<Integer> wrapper = new BTreeNodeWrapper<>(root, height);
stack.push(wrapper);
while (!stack.isEmpty()) {
BTreeNodeWrapper<Integer> current = stack.pop();
if (height < current.height) {
height = current.height;
}
BTreeNode<Integer>[] children = current.node.children;
for (int i = 0; i < children.length; i++) {
if (children[i] != null) {
wrapper = new BTreeNodeWrapper<>(children[i],
current.height + 1);
stack.push(wrapper);
}
}
}
return height;
}
@Test
public void testHeightBTree() {
BTreeNode<Integer> node = new BTreeNode<>(3, false);
node.keys = new Integer[] { 10 };
node.children[0] = new BTreeNode<>(3, false);
node.children[0].keys = new Integer[] { 5 };
node.children[2] = new BTreeNode<>(3, false);
node.children[2].keys = new Integer[] { 13 };
node.children[0].children[2] = new BTreeNode<>(3, true);
node.children[0].children[2].keys = new Integer[] { 9 };
node.children[2].children[2] = new BTreeNode<>(3, false);
node.children[2].children[2].keys = new Integer[] { 17 };
node.children[2].children[2].children[2] = new BTreeNode<>(3, true);
node.children[2].children[2].children[2].keys = new Integer[] { 19 };
int height = height(node);
Assert.assertEquals(3, height);
}
}
package binarytree;
public class Node<T> {
T value;
Node<T> left;
Node<T> right;
public Node(T value, Node<T> left, Node<T> right) {
this.value = value;
this.left = left;
this.right = right;
}
public Node(T value) {
this(value, null, null);
}
public String toString() {
return "[Node:[value: " + this.value + "]]";
}
}
package binarytree;
import java.lang.reflect.Array;
public class BTreeNode<T> {
T[] keys;
BTreeNode<T>[] children;
int t; // number of keys
boolean isLeaf;
@SuppressWarnings("unchecked")
public BTreeNode(int t, boolean isLeaf){
this.t = t;
this.isLeaf = isLeaf;
keys = (T[])Array.newInstance(Object.class, 2*t -1);
children = new BTreeNode[2*t];
}
}
The correct solution is to use stack and get its size at the end of path, but it's important to avoid infinite recursion. So we need to mark branches, we have already processed: if we've already gone to left subtree, we need to mark its root as visitited:
public static int height(Node root) {
LinkedList<Node> stack = new LinkedList<>();
stack.add(root);
Set<Node> marked = new HashSet<>();
int maxHeight = 0;
while (!stack.isEmpty()) {
Node last = stack.getLast();
if (last.left != null && !marked.contains(last.left)) {
stack.addLast(last.left);
marked.add(last.left);
}
else if (last.right != null && !marked.contains(last.right)) {
stack.addLast(last.right);
marked.add(last.right);
}
else {
maxHeight = Math.max(maxHeight, stack.size());
stack.removeLast();
}
}
return maxHeight;
}
public static void main(String[] args) {
Node root = new Node(null, 8);
root.add(4);
root.add(2);
root.add(6);
root.add(7);
root.add(15);
root.add(17);
root.add(19);
root.add(11);
System.out.println(height(root));
}
For multi-children variant we do the same but just iterate through children looking for unmarked nodes:
while (!stack.isEmpty()) {
Node last = stack.getLast();
Node child;
if ((child = findNextNotMarked(last.children, marked)) != null) {
stack.addLast(child);
marked.add(child);
}
else {
maxHeight = Math.max(maxHeight, stack.size());
stack.removeLast();
}
}
int height =0;
int max_height =0;
do
{
stack.add(tree);
height ++;
while(tree != null)
{
stack.add(tree->left);
height = height +1;
tree = tree -> left;
}
if(height > max_height)
max_height = height;
tree = stack.pop();
height = height -1;
while( tree <0 ||tree->right != null)
{
if(tree < 0)
tree= - tree;
tree = stack.pop();
height = height -1;
}
p = -tree;
stack.add(p);
height = height +1;
tree = tree-> right;
}while(!stack.isEmpty())
public void getheight(Node root)
{
int elementscnt=0;
Node p=root;
Queue<Node> queue=new PriorityQueue<Node>();
if(p!=null)
{
queue.add(p);
elementscnt+=1;
}
while(!queue.isEmpty())
{
p=queue.poll();
System.out.println(p.key);
if(p.left!=null)
{
queue.add(p.left);
elementscnt+=1;
}
if(p.right!=null)
{
queue.add(p.right);
elementscnt+=1;
}
}
double height=Math.log(elementscnt+1)/Math.log(2.0);
}
/*
- g September 25, 2014* use Depth First Search approach and pre-order tree traversal
* push current node and its current node height into the stacks, s1 and s2
* use a local variable height to keep track on the maximum tree height
*/
public void getHeight(Node p)
{
int height = 0; //keep track on the max tree height
Stack s1 = new Stack(); //keep track on the tree node
Stack s2 = new Stack(); //parallel with s1 to keep track on the tree node height
if (p!= null)
{
s1.push(p);
s2.push(1);
}
while (!s1.isEmpty())
{
p = s1.pop();
level = s2.pop();
if (level > height) //update maximum tree height
height = level;
if (p.left != null)
{
s1.push(p.left);
s2.push(level+1);
}
if (p.right != null)
{
s1.push(p.right);
s2.push(level++);
}
}
return level;
}