## Interview Question

Country: United States

Comment hidden because of low score. Click to expand.
0
of 0 vote

If there is a parent pointer, we can write a method which finds the successor of a given node.

So C# code might be something like this

``````class InorderIterator <T> {
public InorderIterator (BinTree<T> tree) {
if (tree == null) throw ...;
_root = tree;
_current = null;
_firstMove = true;
}
public T Current {
get {
if (_current == null) throw ...;
return _current.Data;
}
}

public bool MoveNext() {
if (_firstMove) {
_current = getSmallest(_root);
_firstMove = false;
return true;
} else {
_current = getSuccessor(_current);
if (_current == null) {
return false;
}
return true;
}
}

public void Reset() {
_firstMove = true;
_current = null;
}

private BinTree<T> getSmallest(BinTree<T> node) {
while (node.Left != null) {
node = node.Left;
}
return node;
}

private BinTree<T> getSuccessor(BinTree <T> node) {
if (node.Right != null) {
return getSmallest(node.Right);
}
BinTree<T> parent = node.Parent;
BinTree <T> current = node;
while (parent && parent.Right == current) {
current = parent;
parent = parent.Parent;
}
return parent;
}

private BinTree<T> _root;
private BinTree<T> _current;
private bool _firstMove;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution does an initial inorder traversal of the tree and populating the queue with the nodes inorder.

``````class Node{
public int data;
public Node left;
public Node right;
}
public class InorderTreeIterator implements Iterator {
Node currentNode;

public InorderTreeIterator(Node root){
initializeQueue(root);
}
public boolean hasNext(){
return(!nodeQueue.empty());
}
public Node next(){
if(hasNext())
return(nodeQueue.removeFirst());
return(null);
}
private initializeQueue(Node root){
if(root = null)
return;
initializeQueue(root.left);
initializeQueue(root.right);
}
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.